Recherche dichotomique dans un tableau trié : principe, programme et coût
Écrire et exécuter à la main une recherche dichotomique dans un tableau trié en Python, justifier sa terminaison par un invariant et comparer son nombre de comparaisons à celui d'une recherche linéaire.

Les points essentiels
- La recherche dichotomique ne s'applique qu'à un tableau déjà trié (ordre croissant ici) : sur un tableau non trié, elle peut passer à côté d'un élément présent et donner un résultat faux.
- Principe : on compare la valeur cherchée à l'élément du milieu de la zone de recherche ; selon le résultat, on garde la moitié gauche, la moitié droite, ou on s'arrête car l'élément est trouvé.
Les mots à connaître
- Recherche dichotomique
- Algorithme de recherche dans un tableau trié qui compare la valeur cherchée à l'élément central de la zone courante puis élimine la moitié de cette zone qui ne peut pas contenir la valeur, jusqu'à trouver l'élément ou obtenir une zone vide.
- Invariant de boucle
- Propriété vraie avant la boucle, conservée à chaque tour, et qui, combinée à la condition de sortie, prouve le résultat. Ici : si la valeur est dans le tableau, elle est entre les indices debut et fin.
Un exemple pour comprendre
Soit le tableau trié t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. On exécute à la main la recherche dichotomique de la valeur 23 en notant à chaque tour debut, fin, milieu et la comparaison effectuée.
Départ : debut = 0, fin = 9. Tour 1 : milieu = (0+9)//2 = 4, t[4] = 16. Comme 16 < 23, la valeur est à droite : debut = 5. Tour 2 : debut = 5, fin = 9, milieu = (5+9)//2 = 7, t[7] = 56. Comme 56 > 23, on garde la gauche : fin = 6. Tour 3 : debut = 5, fin = 6, milieu = (5+6)//2 = 5, t[5] = 23. Égalité : on renvoie l'indice 5. Bilan : 3 comparaisons, alors qu'une recherche linéaire en aurait fait 6 (on parcourt les indices 0 à 5).

