Professeur B. Articles IPT Sup IPT Spé




articles / dichoto



Recherche dichotomique dans
une liste triée
Où l'on fait une recherche efficace, et l'on prouve que ce que l'on fait est correct…

IPT Sup NSI 1ère Algo




Dans cet article, nous nous intéressons à l'algorithme de recherche dichotomique dans une liste triée.
Nous présentons l'algorithme de base, quelques variantes en comparant leurs vitesses, et parlons preuve
de programme.



Présentation de l'algorithme
L'idée de base est simple :

On dispose d'un tableau t trié de valeurs, et on cherche à déterminer si une valeur v est présente
dans le tableau.
Pour cela, on procède par dichotomie :
 On regarde l'élément du milieu du tableau et on le compare à v .
S'ils sont égaux, on a gagné, sinon, on poursuit la recherche dans la première ou la second
moitié du tableau.
Si à la fin, on a réduit la portion du tableau au point qu'il ne contient plus aucun élément, la
recherche s'arrête sur un echec : v n'est pas présent dans t .

Illustrons cela :



22




3 7 11 17 18 19 24 26 30 32 38 39
1 2 3 4 5 6 7 8 9 10 11 12



Nouvelles valeurs Rechercher

Voilà pour la théorie, passons à la pratique. Et là, cela se complique. C'est un problème connu que cet
algorithme est délicat à programmer sans erreur (voir la page Wikipedia en anglais à ce sujet et plus
particulièrement là).


Although the basic idea of binary search is comparatively straightforward, the details can be
surprisingly tricky, and many good programmers have done it wrong the first few times they
tried.
— D. E. Knuth, The Art of Computer Programming
Pour bien comprendre le comportement de l'algorithme et donc le programmer correctement, il est
indispensable d'avoir au moins une petite idée de la correction et de la terminaison de l'algorithme. Pour
le premier, la notion d'invariant de boucle permet de formaliser cela.


Invariants de boucle, petit rappel
Exposons brièvement quelques idées sur les invariants de boucle. On peut les voir comme la version
« preuve de programmes » de l'hypothèse de récurrence. Dans une démonstration par récurrence, on a
typiquement une hypothèse de récurrence Pn que l'on utilise dans deux étapes :

lors de l'initialisation, pour montrer qu'à un certain rang n0 de départ, l'hypothèse de récurrence est
bien vérifiée,
lors de l'hérédité, pour montrer que que si l'hypothèse de récurrence est vrai à un certain rang n
(supérieur ou égal à n0 ), elle est aussi vraie au rang suivant n + 1 :

Pn ⟹ Pn+1

On peut alors en déduire que l'hypothèse de récurrence est vrai pour tout rang supérieur à n0 :

∀ n ≥ n0 , Pn

Un invariant de boucle procède de la même idée :

Si une propriété est vrai en entrant dans une boucle,
et si elle est préservée par le corps de la boucle (autrement dit si elle est vérifiée au début, elle l'est
encore après exécution du corps de la boucle),

alors elle vérifiée à chaque entrée de boucle… et aussi en sortant de la boucle (on parle ici d'une boucle
while ).
La version classique de l'algorithme
On peut écrire l'algorithme ainsi :


def dichotomie(t, v):
a = 0
b = len(t) - 1
while a <= b:
m = (a + b) // 2
if t[m] == v:
# on a trouvé v
return True
elif t[m] < v:
a = m + 1
else:
b = m - 1
# on a a > b
return False


Les variables a et b représentent les bornes entre lesquels on recherche v dans t . Autrement dit,
avec les notations de Python, on cherche v dans t[a:b + 1] . Comment exprimer cela proprement en
termes d'invariants ?


Preuve de correction
Ici, notre invariant est :

v ∈ t ⟹ v ∈ t[a : b + 1]

Autrement dit, si v est présente dans t , alors c'est nécessairement entre les indices a et b (inclus).
Pour prouver qu'il s'agit bien d'un invariant de boucle, on va supposer que notre propriété est vérifiée au
début du corps de la boucle, et on va prouver que c'est encore le cas à la fin.

Après avoir défini m , examinons les tests successifs. Tout d'abord, si l'on a bien t[m] == v , alors on
renvoie True ce qui est correct, ayant effectivement m dans t . Dans ce cas, l'invariant ne sert à rien
puisque l'on a effectivement trouvé l'élément recherché.

Maintenant, deux cas sont possibles :

si t[m] < v , puisque t est trié, la valeur v ne peut pas être présente dans t[a:m + 1] . Ainsi,
si v in t[a:b + 1] , alors nécessairement v in t[m + 1:b + 1] . Ainsi, en posant a = m +
1 , on a v in t[a:b + 1] .
Sinon, sachant de plus que t[m] != v , cela signifie que t[m] > v et donc que si v in t[a:b
+ 1] , alors v in t[a:m] . Ainsi, en posant b = m - 1 , on a v in t[a:b + 1] .

Dans tous les cas, à la fin de l'exécution de la boucle (si l'on y est toujours), la propriété

v ∈ t ⟹ v ∈ t[a : b + 1]

est encore vérifiée. C'est donc bien un invariant de la boucle.

Ce que l'on vient de prouver correspond à la phase d'hérédité d'une démonstration par récurrence. Pour
terminer ce type de démonstration, il faut aussi une phase d'initialisation. Ainsi, si notre hypothèse de
récurrence est vérifiée pour un certain rang, et qu'elle est préservée en passant d'un rang au suivant,
alors elle est vérifiée pour tous les rangs suivants.

De même, vérifions que notre invariant est vérifié avant d'entrer dans la boucle. À ce moment, on a a ==
0 et b == len(t) - 1 et donc t[a:b + 1] == t[0:len(t)] == t . Notre invariant correspond
alors à la tautologie

v ∈ t ⟹ v ∈ t,

il est donc bien vérifié.
Pour résumer, notre propriété est vérifiée en entrée de boucle et c'est un invariant de la boucle. En
conséquent, elle reste vérifiée en sortant de la boucle (quelque soit le nombre d'itérations effectué). De
plus, à ce moment, on a a > b et donc t[a:b + 1] = [] et on peut donc affirmer que v in t =>
v in [] .

Comme v in [] est nécessairement faux, puisque la liste vide ne contient aucune valeur, on en déduit
que v not in t : on peut conclure qu'en sortie de boucle, v n'est pas présent dans la liste.

Comme annoncé précédemment, notre invariant de boucle ne sert pas à montrer la correction en cas de
succés (puisque l'on a effectivement trouvé un indice m tel que t[m] == v ) mais en cas d'échec : bien
que l'on n'a pas inspecté toutes les valeurs de t , on a prouvé que v n'est pas présent dans t . On a
cherché aux bons endroits et puisque l'on n'a pas trouvé cette valeur, cela signifie qu'elle n'y est pas.


Terminaison
Insistons sur le fait que la présence d'un invariant de boucle ne présume en rien de la terminaison de
l'algorithme ; il ne prouve pas que l'on va sortir de la boucle. Par contre, si l'on sort de la boucle, alors le
résultat est correct.

Pour la terminaison, prouvons que si au début d'une itération, a et b sont tels que b − a ≤ 2n − 2
pour un certain entier n, alors à la fin de l'itération, on a

b − a ≤ 2n−1 − 2

En effet, on a

b−a b−a
m−a=⌊ ⌋ et b−m=⌈ ⌉
2 2
et, par croissance de ⌊⋅ ⌋ et ⌈ ⋅ ⌉, si b − a ≤ 2n − 2, alors m − a et b − m sont tous les deux
inférieurs ou égaux à 2n−1 − 1. Ainsi, dans tous les cas, après l'affectation a = m + 1 ou b = m -
1 , on a bien
1
 b − a ≤ 2n−1 − 2

L'exposant de 2 dans la majoration décroit donc de 1 à chaque itération, etaprès un nombre
suffisamment grand d'itérations, l'écart b - a va donc devenir négatif, ce qui est incompatible avec la
condition de boucle b >= a .

Ainsi, on est sûr de sortir de la boucle, l'algorithme termine.


Analyse de complexité
La preuve précédente de terminaison nous permet de déterminer la complexité au pire des cas de
l'algorithme. En effet, le corps de la boucle est en O(1) et si ℓ − 1 ≤ 2n − 2 (avec ℓ la longueur de t ),
alors on effectue au maximum n itérations successives avec

n = ⌈log2 (ℓ + 1)⌉ = ⌊log2 (ℓ) + 1⌋

La complexité au pire des cas est donc en O(log2 ℓ).



Une autre version
Dans la version « classique » de l'algorithme, on effectue deux tests par itération, puisque l'on effectue le
test d'égalité à chaque fois. On peut accélerer l'algorithme en ne faisant qu'un unique test d'égalité, en
sortie de boucle. Elle décrite ici et peut s'écrire ainsi en Python (avec un peu de refactoring, puisque la
variable a correspond à L du code original tandis que b correspond à R + 1 ) :


def dicho2(t, v):
a = 0
b = len(t)
if b == 0:
# il faut traîter le cas
# où la liste est vide
 return False
while b > a + 1:
m = (a + b) // 2
...