À retenir
- Nécessite impérativement une liste triée (croissante ou décroissante).
- Divise la charge de travail par deux à chaque comparaison.
- Extrêmement performante sur les grandes masses de données (complexité logarithmique).
La recherche par dichotomie est une technique très rapide pour trouver un élément précis dans une liste préalablement triée. Au lieu de regarder chaque élément un par un, on ouvre la liste pile au milieu : si l'élément cherché est plus petit, on recommence dans la moitié gauche ; s'il est plus grand, on cherche dans la moitié droite. C'est exactement la méthode que l'on utilise instinctivement pour chercher un mot dans un dictionnaire papier.
Étymologie
Vient du grec dikhotomia, signifiant « division en deux ». En informatique, le terme s'est imposé pour décrire les algorithmes de type « diviser pour régner », où l'on réduit l'espace de travail par deux à chaque étape.
Exemples d'usage
- Chercher un utilisateur par son identifiant numérique dans une base de données classée.
- Trouver un mot dans un dictionnaire électronique.
- Le jeu du « Plus ou Moins » où l'on doit deviner un nombre entre 1 et 100 en recevant des indications à chaque tentative.
Cas d'usage
On l'utilise principalement dans le développement logiciel et les bases de données lorsqu'on doit effectuer des recherches fréquentes sur de très gros volumes de données. C'est le fondement de nombreuses structures de données optimisées comme les arbres binaires de recherche.
Bonnes pratiques
La condition absolue est que les données soient triées. Si vous ajoutez souvent de nouveaux éléments, le coût du tri régulier doit être mis en balance avec le gain de temps de la recherche. Pour de toutes petites listes (moins de 10 éléments), une recherche simple peut être aussi efficace et moins complexe à coder.
Synonymes
Antonymes
Conseil
Si vous apprenez la programmation, essayez d'implémenter cet algorithme manuellement. C'est l'exercice parfait pour comprendre la notion de complexité algorithmique et l'importance de l'organisation des données.
Questions fréquentes
Pourquoi ne pas l'utiliser tout le temps ?
Parce qu'elle demande que les données soient triées. Si vos données changent tout le temps de place ou ne sont pas classées, le temps passé à les trier sera plus long que le gain de la recherche.
Est-ce vraiment plus rapide qu'une recherche ligne par ligne ?
Oui, massivement. Pour chercher dans une liste de 1 million d'éléments, une recherche classique peut faire 1 million d'étapes, alors que la dichotomie n'en fera que 20 au maximum.