Une recherche dichotomique trouve un nom parmi un million en vingt essais

Diviser par deux, encore et encore

Pour chercher un mot dans un dictionnaire, personne ne commence à la première page. On ouvre au milieu, on regarde si le mot cherché est avant ou après, et on recommence sur la moitié restante.

Chaque étape divise le problème par deux. Pour un million d'éléments triés, il faut au pire 20 comparaisons ; pour un milliard, seulement 30. Une recherche séquentielle en demanderait en moyenne 500 000 et 500 millions.

On note cette croissance O(log n) : le temps augmente comme le logarithme de la taille des données. C'est la différence entre un programme qui tient la charge et un programme qui s'effondre.

Condition indispensable : les données doivent être triées. C'est ce qui justifie le coût du tri initial, amorti sur toutes les recherches suivantes.