Première · Numérique et sciences informatiques

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.

Aperçu gratuit
Illustration de la fiche « Recherche dichotomique dans un tableau trié : principe, programme et coût »

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).

Première page de l’Essentiel : Recherche dichotomique dans un tableau trié : principe, programme et coût
Ketty