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é. Travaillant avec le principe de diviser pour conquérir, cet algorithme de recherche peut être assez rapide, mais la mise en garde est que les données doivent être triées. 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 descendante du tableau.
Une recherche binaire est également appelée recherche demi-intervalle ou recherche logarithmique.
Definir Tech 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 commandé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.
- La cible de 8 est comparée à 6. Puisque 6 est plus petit que 8, la cible 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 se déplace vers la valeur immédiatement supérieure.
- Le pointeur est maintenant sur 8. En comparant ceci à la cible, c'est une correspondance exacte, donc la cible a été trouvée.
En utilisant la recherche binaire, la cible n'a dû être comparée qu'à trois valeurs. Comparé à une recherche linéaire, il aurait commencé à partir de la toute première valeur et remonté, 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 au hasard, alors une recherche linéaire donnerait des résultats tout le temps tandis qu'une recherche binaire serait probablement bloquée dans une boucle infinie.