Table des matières:
Définition - Que signifie la recherche binaire?
Un algorithme de recherche binaire est utilisé pour trouver la position d'une valeur spécifique contenue dans un tableau trié. En travaillant avec le principe de diviser pour régner, cet algorithme de recherche peut être assez rapide, mais la mise en garde est que les données doivent être sous une forme triée. Cela fonctionne en commençant la recherche au milieu du tableau et en descendant 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, elle doit regarder la partie décroissante du tableau.
Une recherche binaire est également appelée recherche à demi-intervalle ou recherche logarithmique.
Techopedia explique la recherche binaire
Une recherche binaire est une méthode rapide et efficace pour trouver une valeur cible spécifique à partir d'un ensemble d'articles ordonnés. En commençant au milieu de la liste triée, il peut effectivement réduire de moitié 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 médiane / moyenne est trouvée et le pointeur y est défini, qui dans ce cas est 6.
- L'objectif de 8 est comparé à 6. Puisque 6 est inférieur à 8, l'objectif doit être dans la moitié supérieure.
- Le pointeur est déplacé sur la valeur suivante (7) et comparé à la cible. Il est plus petit, donc le pointeur passe à la valeur immédiatement supérieure.
- Le pointeur est maintenant sur 8. En comparant cela à la cible, c'est une correspondance exacte, donc la cible a été trouvée.
En utilisant la recherche binaire, la cible devait seulement être comparée à trois valeurs. Par rapport à une recherche linéaire, elle serait partie de la toute première valeur et remontée, nécessitant de comparer la cible à huit valeurs. Une recherche binaire n'est possible qu'avec un ensemble ordonné de données; si les données sont disposées de manière aléatoire, une recherche linéaire produirait des résultats tout le temps tandis qu'une recherche binaire serait probablement bloquée dans une boucle infinie.
