Livre_silo 30 août 2013 16:32 Page 156
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
156
Informatique pour tous
Une autre manière de signaler l’échec aurait consisté à utiliser une valeur entière non significative. Cependant, la solution avec None est plus robuste, par exemple car elle empêchera
de traiter ce résultat comme un entier significatif dans un code qui appelle la fonction
indice.
6.3.2 Recherche dichotomique dans un tableau trié
On note que dans le pire des cas, les fonctions appartient et indice précédentes parcourent
tout le tableau et effectuent donc n comparaisons, où n est la longueur du tableau. Dans
certains cas, cependant, la recherche d’un élément dans un tableau peut être réalisée de
manière plus efficace. C’est le cas par exemple lorsque le tableau est trié. On peut alors
exploiter l’idée suivante : on coupe le tableau en deux par le milieu et on détermine si la
valeur x doit être recherchée dans la moitié gauche ou droite. En effet, il suffit pour cela de
la comparer avec la valeur centrale. Puis, on répète le processus sur la portion sélectionnée.
On suppose par exemple que l’on cherche la valeur 9 dans le tableau [1, 3, 5, 6, 9, 12, 14].
La recherche s’effectue ainsi :
On cherche dans a[0:7].
1 3 5 6 9 12 14
On compare x=9 avec a[3]=6.
1 3 5 6 9 12 14
On cherche dans a[4:7].
9 12 14
On compare x=9 avec a[5]=12.
9 12 14
On cherche dans a[4:4].
9
On compare x=9 avec a[4]=9.
9
Seules trois comparaisons ont été nécessaires pour trouver la valeur. C’est une application
du principe diviser pour régner. On retrouvera d’autres applications de ce principe dans les
chapitres 8 consacré à la résolution d’équations et 13 consacré aux tris.
Pour écrire l’algorithme, on délimite la portion du tableau a dans laquelle la valeur x doit
être recherchée à l’aide de deux indices g et d. On maintient l’invariant suivant : les valeurs strictement à gauche de g sont inférieures à x et les valeurs strictement à droite de d
supérieures à x, ce qui s’illustre ainsi :
0
g
d
n
< x
?
> x
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
156
Informatique pour tous
Une autre manière de signaler l’échec aurait consisté à utiliser une valeur entière non significative. Cependant, la solution avec None est plus robuste, par exemple car elle empêchera
de traiter ce résultat comme un entier significatif dans un code qui appelle la fonction
indice.
6.3.2 Recherche dichotomique dans un tableau trié
On note que dans le pire des cas, les fonctions appartient et indice précédentes parcourent
tout le tableau et effectuent donc n comparaisons, où n est la longueur du tableau. Dans
certains cas, cependant, la recherche d’un élément dans un tableau peut être réalisée de
manière plus efficace. C’est le cas par exemple lorsque le tableau est trié. On peut alors
exploiter l’idée suivante : on coupe le tableau en deux par le milieu et on détermine si la
valeur x doit être recherchée dans la moitié gauche ou droite. En effet, il suffit pour cela de
la comparer avec la valeur centrale. Puis, on répète le processus sur la portion sélectionnée.
On suppose par exemple que l’on cherche la valeur 9 dans le tableau [1, 3, 5, 6, 9, 12, 14].
La recherche s’effectue ainsi :
On cherche dans a[0:7].
1 3 5 6 9 12 14
On compare x=9 avec a[3]=6.
1 3 5 6 9 12 14
On cherche dans a[4:7].
9 12 14
On compare x=9 avec a[5]=12.
9 12 14
On cherche dans a[4:4].
9
On compare x=9 avec a[4]=9.
9
Seules trois comparaisons ont été nécessaires pour trouver la valeur. C’est une application
du principe diviser pour régner. On retrouvera d’autres applications de ce principe dans les
chapitres 8 consacré à la résolution d’équations et 13 consacré aux tris.
Pour écrire l’algorithme, on délimite la portion du tableau a dans laquelle la valeur x doit
être recherchée à l’aide de deux indices g et d. On maintient l’invariant suivant : les valeurs strictement à gauche de g sont inférieures à x et les valeurs strictement à droite de d
supérieures à x, ce qui s’illustre ainsi :
0
g
d
n
< x
?
> x