Recherche dichotomique

En informatique, rechercher un élément dans un tableau est un problème récurrent et parfois coûteux. Nous allons voir ici une méthode simple permettant de trouver un élément dans un tableau trié. Grâce à cette propriété nous allons voir comment diminuer drastiquement le nombre d’itérations nécessaires, donc la complexité et le cout. La recherche dichotomique, également connue sous le nom de recherche binaire, est une technique algorithmique utilisée pour trouver la position d’une valeur cible dans une liste ou un tableau trié.

Cet article adopte les principes de la sémantique axiomatique développée par C.A.R. Hoare pour démontrer la correction et l’efficacité de cet algorithme fondamental. L’idée de base de la recherche dichotomique est de diviser la liste en deux de manière répétée et d’écarter la moitié des éléments restants en les comparant à la valeur cible, jusqu’à ce que cette dernière soit trouvée ou que la liste soit épuisée. On peut donc écrire cette première propriété :

• (1) $\forall i, j \in [0, N] \mid i < j \land T[i] < T[j] \Rightarrow \text{triée}$

La recherche dichotomique consiste à diviser l’espace de recherche (valeur = valeur recherchée). En effet, il en résulte que, grâce à la propriété (1) si T[i]