Couper l'intervalle en deux

Imagine que tu cherches un mot dans un dictionnaire papier. Tu ne lis pas page par page depuis le début : tu ouvres au milieu, tu regardes si le mot cherché est avant ou après, puis tu recommences sur la moitié restante. C'est exactement le principe de la recherche dichotomique : elle ne fonctionne QUE sur un tableau déjà trié, et elle élimine la moitié des candidats à chaque étape.

On maintient deux bornes, gauche et droite, qui délimitent la zone où la valeur cherchée (la « cible ») peut encore se trouver. On calcule le milieu de cette zone, on compare la valeur à cet indice avec la cible : si elles sont égales, on a trouvé ; si la valeur du milieu est plus petite que la cible, la cible ne peut être qu'à droite du milieu (on déplace gauche) ; sinon elle ne peut être qu'à gauche (on déplace droite).

Suivons l'intervalle [gauche, droite] se réduire en cherchant la valeur 25 dans le tableau trié des nombres impairs de 1 à 31 (indices 0 à 15) :

tableau (indice:valeur) : 0:1 1:3 2:5 3:7 4:9 5:11 6:13 7:15 8:17 9:19 10:21 11:23 12:25 13:27 14:29 15:31

etape 1 : [gauche=0  ......milieu=7(valeur 15)...... droite=15]   (15 < 25 -> on garde la moitie de droite)
etape 2 :            [gauche=8...milieu=11(valeur 23)... droite=15]   (23 < 25 -> on garde la moitie de droite)
etape 3 :                        [gauche=12.milieu=13(valeur 27). droite=15]   (27 > 25 -> on garde la moitie de gauche)
etape 4 :                        [gauche=12=milieu=droite=12(valeur 25)]   (trouve !)

En seulement 4 étapes, on a retrouvé la valeur parmi 16 éléments, alors qu'une recherche linéaire aurait pu nécessiter jusqu'à 16 comparaisons. C'est toute la force de la dichotomie : diviser la zone de recherche par deux à chaque étape au lieu de l'explorer élément par élément.