La recherche dichotomique, ou encore bien connu en anglais sous le nom de “Binary search”, est un algorithme de recherche bien connu en académie et surtout bien implanté dans le domaine pratique. Ça s’apparente aux arbres binaires dont j’ai récemment écrit un article les concernant. Ils sont apparentés dans le sens où les arbres binaires peuvent implémenter efficacement l’algorithme de la recherche dichotomique.
La vidéo en bas de la chaîne YouTube Computerphile expose très bien le concept de l’algorithme, et même que l’idée derrière cet algorithme est assez simple et intuitive. Supposons un ensemble où vous avez des valeurs ou des entrées ordonnées, comme par exemple un dictionnaire, où les entrées sont ordonnées par ordre alphabétique. La méthode la moins efficace pour chercher un mot est de parcourir les entrées une à une du début à la fin du dictionnaire. Mais en réalité, il est plus optimal de commencer la recherche au milieu. En sachant que les entrées sont ordonnées, vous pouvez deviner si la valeur recherchée se trouve dans la moitié inférieure ou dans la moitié supérieure. Vous venez ainsi d’éliminer le temps de recherche sur la moitié de l’ensemble. Et le processus ensuite va se répéter récursivement pour la moitié restante jusqu’à arriver précisément à trouver la position de votre valeur. C’est ainsi le principe de fonctionnement de la recherche dichotomique.
Théoriquement, cette méthode peut à première vue sembler peu efficace, mais en réalité elle est très très puissante. Si par exemple vous avez un dictionnaire d’un million d’entrées, dans le pire des cas, vous aurez à faire 20 opérations pour trouver votre valeur. Alors que dans une recherche avec la méthode basique de parcourir toutes les entrées, dans le pire des cas, vous aurez à faire un million d’opérations. Entre 20 opérations et un million d’opérations il n’y a pas photo, clairement l’algorithme est très efficace. Et ça l’est encore plus avec des ensembles plus grands, puisque la complexité de cet algorithme est logarithmique. C’est vrai que ça semble vertigineux, si vous ne me croyez pas, vous pouvez tester ça vous-même, en utilisant une calculatrice et en divisant la valeur un million par 2, 20 fois.