La recherche binaire est une méthode efficace — son estimation de complexité est O(log2(n)), tandis que la recherche séquentielle conventionnelle a O(n). Cela signifie que, par exemple, pour un tableau de 1024 éléments, une recherche linéaire, dans le pire des cas, lorsque l'élément recherché n'est pas dans le tableau, traitera tous les 1024 éléments. La recherche binaire est suffisante pour traiter les éléments \(log_2(1024) = 10\). Ce résultat est obtenu grâce au fait qu'après la première étape de la boucle, la zone de recherche se réduit à 512 éléments, après la seconde – jusqu'à 256 etc.
Les inconvénients de cet algorithme sont la nécessité d'ordonner les données, ainsi que la possibilité d'accéder à n'importe quel élément de données dans un temps constant (indépendamment de la quantité de données). Ainsi, l'algorithme ne peut pas fonctionner sur des tableaux non ordonnés et sur des structures de données basées sur des listes chaînées.
Mise en œuvre
au revoir (droite – gauche > 1) // Tant que la bordure droite est à droite de la gauche
nc
milieu = (gauche + droite) /< /span> 2 ; // Milieu de la zone de recherche
si (A[moyen] >= b)alors
droite = milieu ; // Déplacer la bordure droite
autrement
gauche = milieu ; // Sinon déplacer le bord gauche
cc
si (A[right] == X)alors
sortie droite ;
autrement
sortie -1 ;
où :
A - tableau source,
N - taille du tableau,
X - le nombre souhaité.
|