Introduction à l'algorithme de recherche linéaire : introduction et fonctionnalités [avec exemples]

Qu'est-ce que la recherche ?

La recherche est le processus de recherche d'un élément donné dans une liste d'éléments. Il aide à la recherche d'un enregistrement particulier. Il s'agit donc d'une technique d'identification de la place d'un élément donné. Le succès d'un processus de recherche dépend du fait que l'élément à rechercher a été identifié ou non.

La structure de données permet la recherche de données par deux méthodes.

1. Recherche linéaire ou recherche séquentielle
2. Recherche binaire

Recherche linéaire

Les algorithmes de recherche linéaire sont un type d'algorithme pour la recherche séquentielle des données. Cet algorithme trouve un élément donné avec une complexité O(n). Il est appliqué à une collection d'éléments. Chaque élément des données est recherché séquentiellement et renvoyé s'il correspond à l'élément recherché. Si aucune correspondance n'est trouvée, la recherche continue jusqu'à la fin des données collectées. Il s'agit essentiellement d'une technique d'exploration de chaque élément tout en parcourant la liste. L'algorithme de recherche peut être appliqué à la fois aux données triées et non triées. La recherche pratiquement linéaire est rarement utilisée en raison des options de recherche plus rapides fournies par d'autres algorithmes de recherche tels que les algorithmes de recherche binaires et les tables de hachage.

Étapes de l'algorithme de recherche linéaire

• Lecture de l'élément de recherche par l'utilisateur.
• L'élément à rechercher est compressé avec le premier élément de la liste.
• Si les éléments correspondent, un retour est généré.
• Si les éléments ne correspondent pas, l'élément à rechercher est comparé au deuxième élément de la liste.
• Le processus est répété jusqu'à ce que l'élément corresponde.

Caractéristiques des algorithmes de recherche linéaire

1. Il est généralement appliqué à une petite liste de données non triées ou non ordonnées.
2. Le temps est linéairement dépendant du nombre d'éléments, donc ayant une complexité temporelle si O(n).
3. La mise en oeuvre est très simple.

Algorithmes de recherche linéaire

Une méthode de boucle continue continue jusqu'à ce que l'élément soit trouvé

• algorithme Seqnl_Search(list, item)
• Pré : liste != ;
• Post : retourne l'index de l'item si trouvé, sinon : 1
• indice <- fi
• while index < list.Cnt and list[index] != item //cnt : variable compteur
• indice <- indice + 1
• fin tandis que
• si index < list.Cnt et list[index] = item
• indice de retour
• fin si
• retour : 1
• fin Seqnl_Search

Exemple de recherche linéaire

Problème : Étant donné un tableau arr[] de n éléments, écrivez une fonction pour rechercher un élément donné x dans arr[].

Figure 1 : Un exemple de code montrant la mise en œuvre de l'algorithme de recherche linéaire

La source

Les algorithmes de recherche linéaire peuvent être utilisés dans plusieurs langages de programmation.

1. Recherche linéaire en Python

Figure 2 : Un exemple de code montrant un algorithme de recherche linéaire en langage Python

La source

Sortie : l'élément est présent à l'index 3

2. Recherche linéaire en C

Figure 3 : Un exemple de code montrant un algorithme de recherche linéaire en langage C

La source

Sortie : L'élément est présent à l'indice 3

3. Recherche linéaire dans la structure de données

Le pseudo-code d'un problème de recherche linéaire dans la structure de données est

Figure 4 : Le pseudocode pour l'algorithme de recherche linéaire

La source

Recherche binaire

La recherche binaire est un algorithme permettant de rechercher des éléments dans un tableau d'éléments. Par rapport à l'algorithme de recherche linéaire, l'algorithme de recherche binaire est appliqué à une liste triée de données.

L'algorithme de recherche binaire comprend les étapes suivantes

• Comparaison de l'élément à rechercher avec l'élément du milieu de la liste ou du tableau.
• Si l'élément correspond à l'élément de la liste, il renvoie l'index de l'élément du milieu.
• Si aucune correspondance n'est renvoyée, il est vérifié si l'élément est supérieur ou inférieur à l'élément du milieu.
• Pour un élément de valeur supérieure à l'élément du milieu, la recherche s'effectue sur le côté droit du tableau.
• De même, si l'élément a une valeur moindre que l'élément du milieu, la recherche est effectuée sur le côté gauche de la liste.

Par conséquent, la recherche binaire est mieux appliquée lorsque les données contiennent un grand nombre d'éléments de tige de manière triée. Cela en fait une condition requise pour l'algorithme de recherche que la liste/le tableau soit trié.

Caractéristiques de la recherche binaire

• L'algorithme de recherche binaire est utile pour rechercher un grand nombre d'éléments dans un tableau.
• L'algorithme de recherche binaire a une complexité temporelle de O(logn).
• L'implémentation d'un algorithme de recherche binaire est simple.

Algorithme de recherche binaire

• Algorithme Binary_Search (liste, élément)
• Réglez L sur 0 et R sur n : 1
• si L > R, alors Binary_Search se termine comme un échec
• autre
• Réglez m (la position dans l'élément médian) au sol de (L + R) / 2
• si Am < T, réglez L sur m + 1 et passez à l'étape 3
• si Am > T, réglez R sur m : 1 et passez à l'étape 3
• Maintenant, Am = T,
• la recherche est terminée ; retour (m)

Conclusion

Dans cet article, nous avons examiné ce qu'est un algorithme de recherche linéaire et avons également étudié en détail comment rechercher un certain élément dans une liste à l'aide de l'algorithme de recherche linéaire. Enfin, nous avons également vu comment nous pouvions pratiquement implémenter l'algorithme de recherche linéaire en utilisant Python 3 comme langage et obtenir le résultat souhaité.

Si vous êtes intéressé par la science des données, vous devez consulter le programme Executive PG de IIIT-B et upGrad en science des données, qui a été soigneusement conçu pour les professionnels en activité et propose de nombreuses études de cas, des ateliers pratiques, un mentorat individuel et beaucoup plus.