Recherche par dichotomie

Cet algorithme sert à chercher un élément dans un tableau trié. Il fonctionne grâce à la remarque suivante: si l'on cherche un élément x dans un tableau T trié de taille n, et que l'on regarde une case T[i] quelconque: En particulier, si l'on regarde au milieu du tableau, on élimine toute une moitié du tableau de la recherche, on peut alors regarder au milieu de la zone restante, et ainsi de suite...

Pseudo-code

Entrée: T un tableau de n éléments, x une valeur à chercher
Sortie: i tel que T[i] = x, ou -1 si x n'est pas dans T

Principe

Les variables a et b marquent le début et la fin de la zone de recherche actuelle. A chaque fois que l'on regarde la case du milieu, on met à jour soit a soit b en conséquence.

Terminaison et complexité

Chaque étape divise par 2 la taille de l'intervalle de recherche, on fait donc O(log n) passages de boucle, et chaque passage est en temps constant, l'algorithme est donc en O(log n).

Correction

Le rôle des variables a et b peut être résumé par les deux invariants suivants:
  • A: "T[0], ... T[a-1] ne contiennent pas x."
  • B: "T[b+1], ... T[n-1] ne contiennent pas x."
Graphiquement, les cases grisées sont garanties de ne pas contenir x. En particulier, lorsque l'algorithme sort de la boucle, on a a > b, et donc les invariants A et B couvrent l'intégralité du tableau: le tableau ne contient pas x du tout.