À retenir
- Une efficacité redoutable sur de très gros volumes de données.
- Nécessite obligatoirement un ensemble de données déjà trié.
- Réduit de moitié le nombre de possibilités à chaque étape (complexité logarithmique).
Se dit d'une méthode de résolution de problème qui consiste à diviser systématiquement un ensemble de données en deux parties égales à chaque étape. C'est l'équivalent informatique du jeu du « plus petit ou plus grand » : on réduit de moitié le champ des recherches jusqu'à trouver la solution.
Étymologie
Issu du grec ancien dikha (en deux) et tomē (coupe). En informatique, le terme s'est imposé pour décrire la recherche binaire, une technique fondamentale d'optimisation de traitement de données apparue avec les premiers algorithmes de tri et de recherche.
Exemples d'usage
- Recherche binaire : Trouver un mot dans un dictionnaire en l'ouvrant toujours au milieu de la section restante.
- Algorithme Git Bisect : Un outil utilisé par les développeurs pour identifier quel changement de code a introduit une erreur en testant par moitiés successives l'historique des modifications.
- Recherche de racine : Méthode mathématique pour trouver une valeur approchée d'une solution en coupant un intervalle en deux.
Cas d'usage
Ce concept intervient principalement dans l'optimisation des recherches au sein de grandes bases de données, dans la conception d'algorithmes de tri performants, ou encore dans le débogage de systèmes complexes où il faut isoler une erreur parmi des milliers de lignes de code.
Bonnes pratiques
L'utilisation d'une approche dichotomique impose une condition absolue : les données doivent être triées. Si vous cherchez un nombre dans une liste désordonnée par cette méthode, le résultat sera totalement erroné. Il faut toujours évaluer si le coût du tri initial est compensé par le gain de vitesse de la recherche.
Synonymes
Antonymes
Conseil
Quand vous devez chercher une information dans un gros volume de données, demandez-vous toujours si elles sont triées. Si c'est le cas, oubliez la recherche classique (un par un) et privilégiez systématiquement une approche dichotomique pour économiser les ressources de votre machine.
Questions fréquentes
Pourquoi dit-on que c'est une méthode rapide ?
Parce que sa progression est spectaculaire : pour trouver un élément parmi un million, une recherche linéaire peut demander un million d'étapes, là où la dichotomie n'en demande que 20.
Peut-on l'utiliser sur n'importe quel type de donnée ?
Oui, à condition que ces données puissent être comparées et ordonnées (nombres, dates, alphabétique, etc.).