Un algorithme de recherche binaire est utilisé pour trouver la position d’une valeur particulière contenue dans un tableau trié. Cet algorithme de recherche, qui utilise le principe du « diviser pour régner », peut être assez rapide, mais sa limite est que les données doivent être sous une forme triée. Il commence à chercher au milieu du tableau et travaille sur la première moitié inférieure ou supérieure de la séquence. Si la valeur médiane est inférieure à la valeur cible, cela signifie que la recherche doit aller plus haut, sinon, il faut regarder la partie descendante du tableau.
Une recherche binaire est également appelée recherche en demi-intervalle ou recherche logarithmique.
La recherche binaire est un moyen rapide et efficace de trouver une valeur cible spécifique dans un ensemble d’éléments ordonnés. En commençant au milieu de la liste triée, il peut effectivement bissecter l’espace de recherche en déterminant s’il faut monter ou descendre la liste en fonction de la valeur médiane par rapport à la valeur cible.
Par exemple, avec une valeur cible de 8 et un espace de recherche de 1 à 11 :
– La valeur moyenne / médiane est trouvée et le pointeur est placé à cet endroit, qui dans ce cas est 6 ;
– L’objectif de 8 est comparé à celui de 6. Comme 6 est plus petit que 8, la cible doit se trouver dans la moitié supérieure ;
– Le pointeur est déplacé vers la valeur suivante (7) et comparé à la cible. Il est plus petit, donc le pointeur se déplace vers la valeur supérieure suivante ;
– Le pointeur est maintenant à 8. Comparez-le à la cible, c’est une correspondance exacte, donc la cible a été trouvée.
Dans la recherche binaire, la cible ne devait être comparée qu’à trois valeurs. Par rapport à une recherche linéaire, elle serait partie de la première valeur et aurait progressé, comparant la cible à huit valeurs. Une recherche binaire n’est possible qu’avec un ensemble ordonné de données ; si les données sont ordonnées de manière aléatoire, une recherche linéaire renverrait continuellement des résultats, tandis qu’une recherche binaire serait probablement bloquée dans une boucle infinie.