Recherche linéaire : Python, C++ Exemple

Qu’est-ce que l’algorithme de recherche ?

Un algorithme de recherche est conçu pour trouver un élément ou un objet dans une collection d'éléments ou d'objets présentant une structure de données donnée. Par exemple, il peut s'agir de rechercher la hauteur minimale dans une liste de hauteurs, ou la valeur maximale dans une liste ou un tableau de nombres. Parmi les algorithmes de recherche les plus courants, on trouve la recherche linéaire, la recherche binaire, la recherche par sauts, la recherche de Fibonacci, etc.

Qu'est-ce que la recherche linéaire ?

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é, elle recherche l'élément recherché élément par élément. La recherche linéaire parcourt toute la liste et vérifie si chaque élément est égal à l'élément recherché. Elle est également appelée… 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é est introuvable 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 ?

Considérons un tableau contenant des nombres entiers. La tâche consiste à trouver un nombre donné dans ce 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) Initialisez 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 (L'élément se trouve à l'index 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.

Faux Code pour l'algorithme de recherche séquentielle

Le pseudocode suivant illustre la logique de la recherche linéaire décrite ci-dessus. Il parcourt le tableau à partir du premier indice et renvoie la position en cas de correspondance, sinon il renvoie -1.

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 a negative index is not valid
    return -1

C++ Code Exemple de recherche linéaire

Voici un complet C++ Programme qui implémente la recherche séquentielle et affiche l'index de la valeur recherchée.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Exemple de recherche linéaire

La même logique dans Python utilise une seule boucle sur les indices de la liste et renvoie la position de l'élément correspondant.

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

De manière générale, la complexité temporelle désigne le temps processeur nécessaire pour effectuer une tâche donnée. Dans l'algorithme de recherche linéaire, cette tâche consiste à trouver la clé de recherche parmi les éléments 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 :

Supposons que nous devions effectuer une recherche linéaire dans un tableau de taille « n ». L’élément recherché se trouve entre les indices 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 recherché.

Dans ce cas, la complexité dans le pire des cas sera O(n). Ici, « O » — notation grand O — désigne la fonction de complexité.

Complexité temporelle de la recherche linéaire dans le scénario Meilleur-Case :

Supposons que nous recherchions l'élément situé en première position du tableau. Dans ce cas, l'algorithme de recherche linéaire ne parcourra pas les n éléments du tableau. Sa complexité sera donc de O(1), c'est-à-dire constante.

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.

Complexité spatiale de l'algorithme de recherche linéaire :

La complexité spatiale de la recherche linéaire est toujours O(N) car nous n'avons pas besoin de stocker ou d'utiliser 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 au cours du cycle de vie du programme. Il est également possible que nous exécutions l'algorithme de recherche linéaire et recherchions une clé spécifique à plusieurs reprises. 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 recherché avec l'élément précédent dans le tableau. Par exemple, supposons que vous ayez 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 data[5] et data[4]. Le tableau de données ressemblera alors à ceci :

Données[] = {1,5,9,8,4,7,3,11}

Vous remarquerez que plus une clé est recherchée fréquemment, plus son index diminue, réduisant ainsi le nombre de comparaisons.

Déplacez-vous vers l'avant :

Dans cette méthode, nous inversons l'élément de recherche et le plaçons à l'indice 0. Ainsi, si une nouvelle recherche est effectuée, nous pouvons le trouver en temps constant (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 les listes ne contenant que quelques éléments, 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.

FAQ