Recherche dichotomique

La recherche dichotomique, c'est chercher un mot dans un dictionnaire : on l'ouvre au milieu, on regarde si le mot vient avant ou après, et on recommence avec cette moitié. Dans une liste triée, elle trouve n'importe quelle valeur parmi un million en 20 comparaisons au plus.

Une rangée triée de barres avec la barre du milieu mise en évidence, la moitié de la rangée estompée et une ligne pointillée à la hauteur de la cible
Une rangée triée de barres avec la barre du milieu mise en évidence, la moitié de la rangée estompée et une ligne pointillée à la hauteur de la cible

L'idée

Dans une liste triée, une comparaison vous apprend plus que si vous avez trouvé la cible : elle vous dit de quel côté se trouve la cible. Comparez la cible à la valeur du milieu. Si elles sont égales, c'est fini. Si la valeur du milieu est plus petite, tout ce qui la précède l'est aussi, donc la cible ne peut être qu'après. Si elle est plus grande, la cible ne peut être qu'avant. Gardez seulement cette moitié et recommencez.

Un exemple

Cherchez 23 dans 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. La valeur du milieu est 16, plus petite : il ne reste que 23 à 91. Leur milieu est 56, plus grand : il ne reste que 23 et 38. Leur milieu est 23 : trouvé à la position 6 en 3 comparaisons, là où la recherche linéaire en demande 6. Chercher 40 dans la même liste compare 16, 56, 23 et 38, après quoi il ne reste rien : 4 comparaisons pour savoir que 40 est absent, contre 10 pour la recherche linéaire.

Diviser par deux, ça va vite

Après une comparaison, il reste au plus la moitié de la liste, après deux un quart, après k au plus environ n/2ᵏ. La recherche s'arrête quand il ne reste rien, donc il lui faut au plus ⌊log₂ n⌋ + 1 comparaisons : 6 pour 40 valeurs, 10 pour 1 000, 20 pour un million et 30 pour un milliard. Doubler la liste n'ajoute qu'une comparaison. On note cela O(log n).

Simple à décrire, difficile à bien écrire

John Mauchly a décrit la recherche dichotomique en 1946, mais selon Donald Knuth, la première version correcte pour toutes les longueurs de liste n'a été publiée qu'en 1962. Jon Bentley a ensuite constaté qu'environ un programmeur professionnel sur dix seulement l'écrivait correctement : les conditions d'arrêt et le plus ou moins un au moment de couper les moitiés sont faciles à rater. En 2006, Joshua Bloch a montré que la façon courante de trouver le milieu, (low + high) / 2, peut déborder pour de très longues listes, un bug resté des années dans la bibliothèque Java. Écrire low + (high − low) / 2, comme le fait l'application, l'évite.

John Mauchly (cinquième à partir de la gauche) avec d’autres responsables de l’ENIAC devant la machine, sur une photographie de l’armée américaine. Mauchly a décrit la recherche dichotomique en 1946.
John Mauchly (cinquième à partir de la gauche) avec d’autres responsables de l’ENIAC devant la machine, sur une photographie de l’armée américaine. Mauchly a décrit la recherche dichotomique en 1946.

Variantes et usages

Avec des doublons, la recherche dichotomique trouve l'une des correspondances ; les versions qui continuent vers la gauche ou la droite trouvent la première ou la dernière, ou la position où insérer une valeur absente. La même idée de division par deux trouve la racine d'une équation (méthode de dichotomie), la version où un bug est apparu (git bisect) et la réponse à de nombreux problèmes d'optimisation. Les arbres binaires de recherche rangent les données pour que chaque recherche suive le même chemin de divisions par deux.

À vous d'essayer

Ouvrez l'application, choisissez une valeur dans Rechercher, puis appuyez sur Étape. La zone ombrée montre où la cible peut encore être ; la valeur du milieu est mise en évidence, et la moitié écartée s'estompe. Les tuiles indiquent combien de valeurs sont encore possibles et combien de comparaisons une recherche linéaire demanderait pour la même valeur. Cherchez une valeur absente, ou prenez 40 barres, pour voir l'écart se creuser.

Questions fréquemment posées

Quelle est la complexité en temps de la recherche dichotomique ?

O(log n) : au plus ⌊log₂ n⌋ + 1 comparaisons pour n valeurs. Dans le meilleur cas, une seule comparaison suffit, quand la cible est au milieu. La version itérative demande O(1) de mémoire supplémentaire.

Quelle différence entre recherche dichotomique et recherche linéaire ?

La recherche linéaire examine chaque valeur à tour de rôle et fonctionne sur n'importe quelle liste, mais peut demander n comparaisons. La recherche dichotomique ne fonctionne que sur une liste triée, mais écarte la moitié du reste à chaque comparaison, d'où environ log₂ n.

Vaut-il la peine de trier une liste juste pour la recherche dichotomique ?

Seulement si vous y cherchez souvent. Trier demande environ n log n étapes, plus qu'une seule recherche linéaire. Une fois la liste triée, chaque recherche suivante coûte très peu.

La recherche dichotomique marche-t-elle sur autre chose que des listes ?

Oui, sur tout ce pour quoi un test indique de quel côté de la réponse vous êtes : une plage de nombres, les versions d'un programme, ou les essais du jeu du plus ou moins.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer la recherche dichotomique