Algorithme de recherche binaire : fonction, avantages, complexité temporelle et spatiale

introduction

Dans tout système informatique, la recherche est l'une des fonctionnalités les plus critiques à développer. Les techniques de recherche sont utilisées dans la récupération de fichiers, l'indexation et de nombreuses autres applications. De nombreuses techniques de recherche sont disponibles. L'une d'elles est la technique de recherche binaire.

Un algorithme de recherche binaire fonctionne sur l'idée de négliger la moitié de la liste à chaque itération. Il continue à diviser la liste jusqu'à ce qu'il trouve la valeur qu'il recherche dans une liste donnée. Un algorithme de recherche binaire est une mise à niveau rapide vers un algorithme de recherche linéaire simple.

Aucune expérience de codage requise. Accompagnement de carrière à 360°. Diplôme PG en Machine Learning & AI de l'IIIT-B et upGrad.

Fonctionnement d'un algorithme de recherche binaire

La première chose à noter est qu'un algorithme de recherche binaire fonctionne toujours sur une liste triée. La première étape logique consiste donc à trier la liste fournie. Après le tri, la médiane de la liste est vérifiée avec la valeur souhaitée.

• Si la valeur souhaitée est égale à la valeur de l'index central, l'index est renvoyé comme réponse.

• Si la valeur cible est inférieure à l'offre de l'index central de la liste, le côté droit de la liste est ignoré.

• Si la valeur souhaitée est supérieure à la valeur de l'index central, la moitié gauche est ignorée.

• Le processus est ensuite répété sur des listes raccourcies jusqu'à ce que la valeur cible soit trouvée.

Exemple 1

Regardons l'algorithme avec un exemple. Supposons qu'il existe une liste avec les numéros suivants :

1, 15, 23, 7, 6, 14, 8, 3, 27

Prenons la valeur souhaitée comme 27. Le nombre total d'éléments dans la liste est 9.

La première étape consiste à trier la liste. Après le tri, la liste ressemblerait à ceci :

1, 3, 6, 7, 8, 14, 15, 23, 27

Comme le nombre d'éléments dans la liste est de neuf, l'index central serait à cinq. La valeur à l'index cinq est 8. La valeur souhaitée, 27, est comparée à la valeur 8. Vérifiez d'abord si la valeur est égale à 8 ou non. Si oui, retournez index et quittez.

Comme 27 est supérieur à 8, nous ignorerions la partie gauche et ne traverserions que le côté droit de la liste. La nouvelle liste à parcourir est :

14, 15, 23, 27

Remarque : En pratique, la liste n'est pas tronquée. Seule l'observation est resserrée. Ainsi, la « nouvelle liste » ne doit pas être confondue avec la création d'une nouvelle liste ou le raccourcissement de la liste originale. Bien qu'il puisse être mis en œuvre avec une nouvelle liste, il y a deux problèmes. Tout d'abord, il y aura une surcharge de mémoire. Chaque nouvelle liste augmentera la complexité de l'espace. Et deuxièmement, les index d'origine doivent être suivis à chaque itération.

Le nouvel index central peut être considéré comme le deuxième ou le troisième élément, selon l'implémentation. Ici, nous considérerons le troisième élément comme central. La valeur 23 est comparée à la valeur 27. Comme la valeur est supérieure à la valeur centrale, nous écarterons la moitié gauche.

La liste à parcourir est :

27

Comme la liste ne contient qu'un seul élément, il est considéré comme l'élément central. Par conséquent, nous comparons la valeur souhaitée avec 27. Lorsqu'elles correspondent, nous renvoyons la valeur d'index de 27 dans la liste d'origine.

Exemple #2

Dans la même liste, supposons que la valeur souhaitée est 2.

Tout d'abord, la valeur centrale huit est comparée à 2. Comme la valeur souhaitée est inférieure à la valeur centrale, nous nous concentrons sur le côté gauche de la liste.

La nouvelle traversée consistera en :

1, 3, 6, 7

Prenons l'élément central comme deuxième élément. La valeur souhaitée deux est comparée à 3. Comme la valeur est encore plus petite, nous réduisons à nouveau le focus vers le côté gauche de la liste.

La nouvelle traversée consistera en :

1

Comme la liste de parcours n'a qu'un seul élément, la valeur est directement comparée à l'élément restant. On voit que les valeurs ne correspondent pas. Par conséquent, nous sortons de la boucle avec un message d'erreur : valeur introuvable .

Certification avancée en science des données, plus de 250 partenaires d'embauche, plus de 300 heures d'apprentissage, 0 % EMI

Complexité temporelle et spatiale

La complexité temporelle de l' algorithme de recherche binaire est O(log n). La complexité temporelle dans le meilleur des cas serait O (1) lorsque l'indice central correspondrait directement à la valeur souhaitée. Le pire scénario pourrait être les valeurs à l'une ou l'autre extrémité de la liste ou des valeurs ne figurant pas dans la liste.

La complexité spatiale de l' algorithme de recherche binaire dépend de l'implémentation de l'algorithme. Il existe deux manières de le mettre en œuvre :

1. Méthode itérative
2. Méthode récursive

Les deux méthodes sont assez similaires, avec deux différences dans la mise en œuvre. Premièrement, il n'y a pas de boucle dans la méthode récursive. Deuxièmement, plutôt que de transmettre les nouvelles valeurs à la prochaine itération de la boucle, il les transmet à la prochaine récursivité. Dans la méthode itérative, les itérations peuvent être contrôlées par les conditions de bouclage, tandis que dans la méthode récursive, le maximum et le minimum sont utilisés comme condition aux limites.

Dans la méthode itérative, la complexité spatiale serait O(1). Alors que dans la méthode récursive, la complexité spatiale serait O (log n).

Avantages

• Un algorithme de recherche binaire est un algorithme de recherche assez simple à mettre en œuvre.

• Il s'agit d'une amélioration significative par rapport à la recherche linéaire et les performances sont presque identiques par rapport à certains des algorithmes de recherche les plus difficiles à mettre en œuvre.

• L' algorithme de recherche binaire divise la liste en deux à chaque itération, plutôt que de parcourir la liste de manière séquentielle. Sur de grandes listes, cette méthode peut être vraiment utile.

Checkout : Classification de l'arbre de décision : tout ce que vous devez savoir

Conclusion

Un algorithme de recherche binaire est un algorithme largement utilisé dans le domaine informatique. Il s'agit d'un algorithme de recherche complet et précis qui peut bien fonctionner sur les grands et les petits ensembles de données. Un algorithme de recherche binaire est un algorithme simple et fiable à mettre en œuvre. Avec l'analyse du temps et de l'espace, les avantages de l'utilisation de cette technique particulière sont évidents.

Si vous êtes curieux d'en savoir plus sur la science des données, consultez le diplôme PG de IIIT-B & upGrad en science des données qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1- on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.