Si la liste sur laquelle est appliquée la recherche d'un élément est triée, le temps de recherche peut être singulièrement diminué en recourant à une méthode permettant d'éliminer la moitié des éléments de la liste à chaque nouvelle itération. Cet algorithme, appelé recherche dichotomique, consiste à comparer l'élément cherché avec l'élément central de la liste. Si l'élément cherché lui est inférieur, il doit se trouver dans la première moitié de la liste; si l'élément cherché lui est supérieur, il doit se trouver dans la deuxième moitié de la liste. En appliquant récursivement cette technique à la moitié choisie, l'algorithme aboutira soit à la position de l'élément cherché, soit à aucune position auquel cas l'élément n'appartient pas à la liste, comme l'illustre la figure ci-dessous:
Déroulement de la recherche dichotomique de l'élément 54 sur une liste d'entiers
Cette méthode utilise deux pointeurs g et d pour délimiter la sous-liste sur laquelle porte la recherche courante. Si la sous-liste devient vide, c'est-à-dire que les pointeurs g et d se croisent, la recherche est infructueuse et l'algorithme s'arrête. Dans tout autre cas, l'indice m est positionné au milieu de l'intervalle et trois possibilités se présentent: l'élément cherché est trouvé à l'aide de l'indice m ou bien l'élément cherché est plus grand que l'élément situé à la position m et alors le pointeur g est repositionné à en m+1 ou finalement l'élément cherché est plus petit que l'élément situé à la position m auquel cas le pointeur d est repositionné en m-1.
A vous de jouer !
En vous basant sur l'exemple présenté ci-dessus, répondez à chacun des points suivants:
Décrivez chacune des étapes de progression de la recherche dichotomique des éléments 35 et 50 appliquée à la liste ordonnée [2, 12, 17, 25, 33, 35, 44, 54, 77, 91] puis indiquez le nombre de comparaisons nécessaires à chacune des recherches.
Déterminez le nombre maximal de comparaisons nécessaires à la recherche d'un élément dans une liste, si celle-ci comporte 100 ou n éléments.
Implémentez la recherche dichotomique en Python de manière itérative et récursive en vous basant sur le squelette téléchargeable ici.
Solution
Les étapes de progression de l'algorithme sur la liste [2, 12, 17, 25, 33, 35, 44, 54, 77, 91] sont les suivantes:
Déroulement de la recherche dichotomique de l'élément 35
Déroulement de la recherche dichotomique de l'élément 50
Le nombre de comparaisons nécessaires à la recherche de 35 est de 5 (chaque étape non concluante nécessite 2 comparaisons) alors que pour montrer que 50 n'appartient pas à la liste, 8 comparaisons sont nécessaires.
Pour compter le nombre maximal de comparaisons nécessaires pour rechercher un élément, il suffit de remarquer qu'à chaque itération de l'algorithme, la moitié des éléments sont écartés de la liste. Par conséquent, en commençant avec une liste de n éléments, environ n/2 seront écartés après la première comparaison. Après la deuxième comparaison, il en restera n/4, puis n/8 après la troisième, n/16 après la quatrième et ainsi de suite. Le pire cas survient lorsque l'algorithme doit procéder ainsi jusqu'à obtenir une sous-liste ne comportant plus qu'un seul élément. Le nombre E de comparaisons nécessaires pour atteindre ce stade vérifie alors les équivalences suivantes:
Comme chaque étape nécessite 2 comparaisons, le nombre C comparaisons nécessaires pour atteindre une sous-liste de longueur 1 est de C=2E.
Une dernière comparaison étant nécessaire pour vérifier si l'élément restant est ou non l'élément cherché, le nombre maximal de comparaisons nécessaires correspond à.
selon que l'élément restant est ou non l'élément cherché.
Algorithmes et structures de données
