Recherche linéaire : Python, C++ Exemple
Sarah Chen
Qu’est-ce que l’algorithme de recherche ?
Un algorithme de recherche est conçu pour trouver un élément ou un objet parmi une collection d'éléments ou d'objets avec une structure de données donnée. Par exemple, recherchez la hauteur minimale dans une liste de hauteurs donnée ou recherchez la note la plus élevée dans une liste ou un tableau de nombres. Peu d'algorithmes de recherche populaires incluent la « Recherche linéaire », la « Recherche binaire », la « Recherche par saut », la « Recherche de Fibonacci », etc.
Qu'est-ce que la recherche linéaire ?
La recherche linéaire est l'un des algorithmes de recherche les plus simples. À partir d'une liste ou d'un tableau donné, il recherche l'élément donné un par un. La recherche linéaire parcourt toute la liste et vérifie si un élément particulier est égal à l'élément de recherche. On l'appelle aussi le recherche séquentielle.
Que fait la fonction de recherche linéaire ?
Un tableau d’entiers est donné par «Numbers", et une variable "item" contient le nombre entier à rechercher.
Désormais, l'algorithme de recherche linéaire peut fournir le résultat suivant :
- "-1"; cela signifie que l'élément donné n'est pas trouvé dans le tableau
- Tout nombre compris entre 0 et n-1 ; signifie que l'élément recherché est trouvé et qu'il renvoie l'index de l'élément sur le tableau. Ici, « n » représente la taille du tableau.
Comment fonctionne la recherche linéaire ?
Disons un tableau contenant des nombres entiers. La tâche consiste à trouver un nombre donné dans le tableau.
- Si le numéro se trouve dans le tableau, nous devons renvoyer l'index de ce numéro.
- Si le nombre donné n'est pas trouvé, il renverra -1.
Dans l'organigramme, « Données » est le tableau d'entiers, « N » est la taille du tableau et « élément » est le nombre que nous voulons rechercher dans le tableau.
Organigramme de l'algorithme de recherche linéaire :
Voici les étapes de l'organigramme :
Étape 1) Lisez l'élément de recherche, « élément ».
Étape 2) Initier i=0 et index=-1
Étape 3) Si je
Étape 4) Si Data[i] est égal à « élément », passez à l'étape 5. Sinon, passez à l'étape 6.
Étape 5) Index = i (Comme l'élément se trouve à l'index no i). Passez à l'étape 8.
Étape 6) je = je +1.
Étape 7) Passez à l'étape 3.
Étape 8) Arrêter.
Pour plus de simplicité, nous fournissons un exemple avec un tableau d’entiers. La recherche linéaire est également applicable dans la chaîne, un tableau d'objets ou une structure.
Pseudo-code pour l'algorithme de recherche séquentielle
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Exemple de code Recherche linéaire
#include < bits / stdc++.h >
using namespace std;
int linearSearch(int * arr, int item, int n) {
int idx = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == item) {
idx = i;
break;
}
}
return idx;
}
int main() {
int array[] = {
1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
};
int n = sizeof(array) / sizeof(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, item, n);
if (idx >= 0) {
cout << item << " is found at index " << idx << endl;
} else {
cout << "Could not find " << item << " in the array" << endl;
}
}
Sortie :
Enter a number to search: -10 -10 is found at index 14
Python Exemple de code Recherche linéaire
def linearSearch(data, item):
for i in range(len(data)):
if data[i] == item:
return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
print("{} is found at index {}".format(item, idx))
else :
print("{} was not found".format(item))
Sortie :
Enter a number to search: -10 -10 is found at index 14
Analyse de la complexité de l'algorithme de recherche linéaire
Généralement, la complexité temporelle signifie la quantité de temps CPU nécessaire pour effectuer une certaine tâche. Dans l'algorithme de recherche linéaire, la tâche consiste à trouver la clé de recherche à partir de l'élément du tableau.
Trois types de complexités temporelles sont :
- Worst Case Scenario
- Meilleur scénario de cas
- Scénario de cas moyen
Complexité temporelle de la recherche linéaire dans le pire des cas :
Disons que nous devons effectuer une recherche linéaire dans un tableau de taille « n ». Nous pouvons trouver l'élément de recherche entre l'index 0 et n-1. Dans le pire des cas, l'algorithme tentera de faire correspondre tous les éléments du tableau avec l'élément de recherche.
Dans ce cas, la complexité la plus défavorable sera O(n). Ici, la notation « O »-big O signifie la fonction de complexité.
Complexité temporelle de la recherche linéaire dans le scénario Meilleur-Case :
Disons que nous recherchons un élément qui réside en première position du tableau. Dans ce scénario, l’algorithme de recherche linéaire ne recherchera pas les n éléments du tableau. La complexité sera donc O(1). Cela signifie un temps constant.
Complexité temporelle de la recherche linéaire dans un scénario de cas moyen :
Lorsqu'un élément est trouvé à l'index médian du tableau, on peut alors dire que la complexité moyenne des cas pour la recherche linéaire est O(N), où N signifie la longueur du tableau.
La complexité spatiale de l'algorithme de recherche linéaire
La complexité spatiale pour la recherche linéaire est toujours O(N) car nous n'avons pas besoin de stocker ou d'utiliser un quelconque type de variable temporaire dans la fonction de recherche linéaire.
Comment améliorer l'algorithme de recherche linéaire
La recherche peut être effectuée plusieurs fois tout au long du cycle de vie du programme. Il est également possible que nous exécutions l'algorithme de recherche linéaire et recherchions plusieurs fois une clé spécifique. Nous pouvons utiliser le "Algorithme de recherche binaire» si le tableau est un tableau trié.
Supposons que le tableau se compose de 10 5000 nombres et que l'élément cible se trouve au 5000 e index. Ainsi, l’algorithme tentera de comparer éléments. Désormais, les comparaisons sont des tâches gourmandes en CPU. Pour optimiser l'algorithme de recherche linéaire, nous avons deux options.
- Transposition
- Déplacer vers l'avant
Transposition:
Dans cette méthode, nous échangerons l'élément de recherche avec son élément précédent dans le tableau. Par exemple, disons que vous avez un tableau comme celui-ci :
Données[] = {1,5,9,8,7,3,4,11}
Maintenant, nous voulons rechercher 4. Étapes de transposition :
Étape 1) « 4 » se trouve à l'index 6. Il a fallu six comparaisons.
Étape 2) Échangez les données[6] et les données[5]. Le tableau de données ressemblera alors à :
Données[] = {1,5,9,8,7,4,3,11}
Étape 3) Recherchez à nouveau 4. Trouvé à l'index 5. Cette fois, il a fallu cinq comparaisons.
Étape 4) Échangez les données [5] et les données [4]. Le tableau de données ressemblera alors à ceci :
Données [] = {1,5,9,8,4,7,3,11}
Maintenant, si vous remarquez, plus une clé est recherchée fréquemment, plus elle diminue l'index. Ainsi, diminuer le nombre de comparaisons.
Déplacez-vous vers l'avant :
Dans cette méthode, nous échangeons l'élément de recherche dans le 0ème index. Parce que si nous le recherchons à nouveau, nous pouvons le trouver au moment O(1).
Application de l'algorithme de recherche linéaire
Voici quelques applications de recherche linéaire que nous pouvons utiliser.
- Pour les tableaux de petite taille ou seulement quelques éléments dans la liste, il est plus facile d'utiliser la recherche linéaire.
- La méthode de recherche linéaire peut être utilisée en simple ou tableaux multidimensionnels ou d'autres structures de données.
- Généralement, la recherche linéaire est simple et efficace pour effectuer une recherche dans les données « non ordonnées ». Nous pouvons facilement récupérer une seule donnée de la liste non ordonnée donnée.