Recherche linéaire vs recherche binaire : différence entre la recherche linéaire et la recherche binaire

introduction

L'allocation de mémoire contiguë dans les langages de programmation fournit une implémentation flexible du stockage de plusieurs points de données. Cela peut être utilisé à son apogée si nous voulons séparer les données et fusionner toutes les données similaires dans une structure de données contiguë comme un tableau, une liste, etc.

L'allocation de mémoire contiguë a de nombreuses implémentations dans des applications du monde réel comme un système d'exploitation dans des ordinateurs, des systèmes de gestion de base de données, etc. Cette structure de données est considérée comme flexible car l'ajout d'un nouveau point de données à un tableau ne nécessite qu'une seule unité de temps, c'est-à-dire ; O(1).

Mais le problème se pose lorsque nous voulons examiner une entrée particulière ou rechercher une entrée particulière car toutes les applications du monde réel reposent sur les commandes d'accès aux données. Et cette tâche doit être suffisamment rapide pour répondre à la vitesse du processeur et de la mémoire.

Il existe différents algorithmes de recherche divisés en fonction du nombre de comparaisons que nous effectuons pour rechercher l'élément.

Si nous comparons chaque point de données dans le tableau pour rechercher un élément, il est alors considéré comme une recherche séquentielle. Mais si nous ne comparons que quelques éléments en sautant certaines des comparaisons, cela est considéré comme une recherche par intervalle. Mais nous avons besoin qu'un tableau soit trié (ordre croissant ou ordre décroissant) pour effectuer une recherche d'intervalle dessus.

La complexité temporelle de la recherche séquentielle est linéaire O(n), et la complexité temporelle de la recherche binaire (un exemple de recherche par intervalle) est O(log n). En outre, il existe d'autres algorithmes de recherche comme la recherche exponentielle, la recherche par saut, etc.

Mais la recherche linéaire et la recherche binaire sont principalement utilisées, où la recherche linéaire concerne des données aléatoires ou non triées et la recherche binaire concerne des données triées et ordonnées. Le hachage est un algorithme de recherche spécial où la complexité temporelle de l'accès à un point de données est O(1).

Passons d'abord en revue les algorithmes de recherche linéaire et de recherche binaire, puis comparons les différences entre la recherche linéaire et la recherche binaire.

Recherche linéaire

Comme déjà discuté, l'algorithme de recherche linéaire compare chaque élément du tableau, et voici le code pour le faire.

Parcourons le code.

Nous avons déclaré une fonction linear_search, qui attend un tableau, une clé entière comme paramètres. Maintenant, nous devons parcourir tous les éléments et comparer s'ils correspondent à notre clé de recherche, nous avons donc écrit une boucle for qui boucle sur le tableau, et à l'intérieur, il y a une boucle if qui vérifie si le nombre à cette position correspond avec la touche de recherche ou non. Si nous trouvons une correspondance, nous renverrons la position. S'il n'y a pas un tel élément dans le tableau, nous renverrons -1 à la fin de la fonction.

Notez que si nous avons plusieurs apparitions du même numéro, alors nous allons retourner la position de sa première occurrence.

Pour en venir à la méthode principale, nous avons déclaré et initialisé un tableau d'entiers. Ensuite, nous initialisons la clé qui doit être recherchée. Ici, nous codons en dur le tableau et la clé, mais vous pouvez le modifier en entrée utilisateur. Maintenant que nous avons la liste des éléments et la clé à rechercher, la méthode de recherche linéaire est appelée et l'index renvoyé est noté. Plus tard, nous vérifions la valeur renvoyée et imprimons l'index si la clé existe, sinon la clé d'impression est introuvable.

Recherche binaire

La recherche binaire est plus optimisée que la recherche linéaire, mais le tableau doit être trié pour appliquer la recherche binaire. Et voici le code pour le faire.

Parcourons le code.

Nous avons déclaré une méthode binary_search qui attend un tableau d'entiers triés et une clé d'entiers comme paramètres. Nous initialisons les variables low, high, mid. Ici bas, haut sont des pointeurs où bas sera à l'indice 0 et haut sera à l'indice n au début. Alors, comment fonctionne la recherche binaire ?

Dans un premier temps, nous calculerons le milieu du bas et du haut. Nous pouvons calculer le milieu comme (bas + haut)/2, mais parfois haut peut être un grand nombre, et l'ajout de bas au haut peut entraîner un débordement d'entier. Donc, calculer le milieu comme bas + (haut-bas) / 2 serait un moyen optimal.

Nous comparerons l'élément au milieu avec la clé de recherche, et nous renverrons l'index si nous trouvons une correspondance. Sinon, nous vérifierons si l'élément médian est supérieur à la clé ou inférieur à la clé. Si le milieu est supérieur, nous devons vérifier uniquement la première moitié du tableau car tous les éléments de la seconde moitié du tableau sont supérieurs à la clé, nous mettrons donc à jour le haut à mi-1.

De même, si mid est inférieur à key, nous devons rechercher dans la seconde moitié du tableau, mettant ainsi à jour le low à mid+1. N'oubliez pas que la recherche binaire est basée sur l'algorithme de diminution et de conquête puisque nous ignorons l'une des moitiés du tableau à chaque itération.

Pour en revenir à notre code, nous avons construit la méthode principale. Initialisé un tableau trié et une clé de recherche, effectué un appel à la recherche binaire et imprimé les résultats.

Maintenant que nous avons parcouru les algorithmes de recherche linéaire et de recherche binaire, comparons les deux algorithmes.

Recherche linéaire vs recherche binaire

Travaillant

• La recherche linéaire parcourt tous les éléments et les compare avec la clé qui doit être recherchée.
• La recherche binaire diminue judicieusement la taille du tableau qui doit être recherché et compare la clé avec l'élément intermédiaire à chaque fois.

Structure de données

• La recherche linéaire est flexible avec toutes les structures de données comme un tableau, une liste, une liste chaînée, etc.
• La recherche binaire ne peut pas être effectuée sur toutes les structures de données car nous avons besoin d'une traversée multidirectionnelle. Ainsi, les structures de données telles que la liste chaînée unique ne peuvent pas être utilisées.

Conditions préalables

• La recherche linéaire peut être effectuée sur tous les types de données, les données peuvent être aléatoires ou triées, l'algorithme reste le même. Donc pas besoin de travaux préalables.
• La recherche binaire ne fonctionne que sur un tableau trié. Le tri d'un tableau est donc une condition préalable à cet algorithme.

Cas d'utilisation

• La recherche linéaire est généralement préférée pour les ensembles de données plus petits et aléatoires.
• La recherche binaire est préférée pour les ensembles de données comparativement plus grands et triés.

Efficacité

• La recherche linéaire est moins efficace dans le cas de grands ensembles de données.
• La recherche binaire est plus efficace dans le cas de jeux de données plus volumineux.

Complexité temporelle

• Dans la recherche linéaire, la complexité du meilleur cas est O (1) où l'élément se trouve au premier index. La complexité dans le pire des cas est O(n) où l'élément se trouve au dernier index ou l'élément n'est pas présent dans le tableau.
• Dans la recherche binaire, la complexité dans le meilleur des cas est O (1) où l'élément se trouve à l'index du milieu. La complexité du pire cas est O( log 2 n).

Essai à vide

Supposons que nous ayons un tableau de taille 10 000.

• Dans une recherche linéaire, la complexité dans le meilleur des cas est O(1) et la complexité dans le pire des cas est O(10000).
• Dans une recherche binaire, la complexité dans le meilleur des cas est O(1) et la complexité dans le pire des cas est O( log 2 10000)=O(13.287).

Conclusion

Nous avons compris l'importance de l'accès aux données dans des tableaux, compris les algorithmes de la recherche linéaire et de la recherche binaire. Parcourir les codes de la recherche linéaire et de la recherche binaire. Comparé les différences entre la recherche linéaire et la recherche binaire, fait un essai pour un exemple de grande taille.

Maintenant que vous connaissez les différences entre la recherche linéaire et la recherche binaire, essayez d'exécuter les deux codes pour un grand ensemble de données sied et comparez le temps d'exécution, commencez à explorer différents algorithmes de recherche et essayez de les implémenter !

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.

Apprenez des cours de science des données en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.