1A.algo - Recherche dichotomique

Recherche dichotomique illustrée. Extrait de Recherche dichotomique, récursive, itérative et le logarithme.

Lorsqu'on décrit n'importe quel algorithme, on évoque toujours son coût, souvent une formule de ce style :

$$O(n^u(\ln_2 n)^v)$$

$u$ et $v$ sont des entiers. $v$ est souvent soit 0, soit 1. Mais d'où vient ce logarithme ? Le premier algorithme auquel on pense et dont le coût correspond au cas $u=0$ et $v=1$ est la recherche dichotomique. Il consiste à chercher un élément dans une liste triée. Le logarithme vient du fait qu'on réduit l'espace de recherche par deux à chaque itération. Fatalement, on trouve très vite l'élément à chercher. Et le logarithme, dans la plupart des algorithmes, vient du fait qu'on divise la dimension du problème par un nombre entier à chaque itération, ici 2.

La recherche dichotomique est assez simple : on part d'une liste triée T et on cherche l'élément v (on suppose qu'il s'y trouve). On procède comme suit :

C'est ce qu'illustre la figure suivante où a désigne le début de la liste, b la fin, m le milieu. A chaque itération, on déplace ces trois positions.

Version itérative

Version récursive

Version récursive 2

L'ajout des parametrès a et b peut paraître un peu lourd. Voici une troisième implémentation en Python (toujours récursive) :

Il ne faut pas oublier m + sinon le résultat peut être décalé dans certains cas. Ensuite, cette version sera un peu moins rapide du fait de la recopie d'une partie de la liste.