À quoi sert l'algorithme de recherche binaire?

Pour rechercher efficacement un élément dans un tableau trié.

L'essence réside dans la comparaison de la valeur recherchée avec l'élément au centre de l'intervalle de recherche actuel. Si elles sont égales, l'élément est trouvé. Si la valeur recherchée est inférieure, la recherche se limite à la moitié gauche ; si elle est supérieure, à la moitié droite. Le processus se répète jusqu'à ce que l'élément soit trouvé ou que l'intervalle de recherche devienne vide.

L'avantage par rapport à la recherche linéaire est la complexité temporelle logarithmique, O(log n), contre O(n) pour la recherche linéaire. Cela la rend beaucoup plus rapide pour de grands tableaux.

Applications:

• Recherche dans les dictionnaires et bases de données (index).
• Algorithmes de tri (par exemple, dans le tri fusion).
• Recherche de l'élément racine d'une équation.
• Recherche dans des structures de données de type arbres B.