Recherche linéaire

1. Algorithme de recherche linéaire
2. Exemple de recherche linéaire
3. Mise en œuvre de l’algorithme de recherche linéaire
4. Complexité de l’algorithme de recherche linéaire

La recherche linéaire est l’algorithme de recherche le plus simple. Elle est également appelée recherche séquentielle car, dans cet algorithme, nous recherchons un élément en parcourant tout le tableau et en comparant chaque élément avec l’élément souhaité pour trouver une correspondance. Si l’élément souhaité est trouvé, alors l’index ou cet élément est renvoyé ; sinon, nous continuons à chercher jusqu’à épuisement du tableau. Nous pouvons également rechercher des occurrences multiples d’un élément à l’intérieur d’un tableau. Il est surtout utilisé pour rechercher des éléments à l’intérieur d’un tableau non trié. Il n’est pas utilisé dans la pratique car il est beaucoup plus lent que la recherche dichotomique.

Algorithme de recherche linéaire

Supposons que nous ayons un tableau non trié A[] contenant n éléments, et nous voulons trouver un élément - X.

Exemple de recherche linéaire

Supposons que nous ayons le tableau: (5, 3, 4, 2, 1, 6).

• Cas 1: Nous voulons rechercher X = 5.

Le premier élément lui-même est une correspondance, et nous renvoyons l’index 0. (Meilleur cas)

• Cas 2: Nous voulons rechercher X = 1.

Nous parcourons le tableau et atteignons l’index 4 pour trouver une correspondance et renvoyer cet index. (Cas moyen)

• Cas 3: Nous voulons rechercher X = 9

Nous parcourons le tableau mais ne trouvons pas de correspondance lorsque nous atteignons le dernier élément du tableau. Nous retournons -1. (Pire cas)

Mise en œuvre de l’algorithme de recherche linéaire

Algorithme de recherche linéaire pour une seule correspondance

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) return i;
  }
  return -1;
}

int main() {
  int n = 5;
  int arr[] = {2, 4, 0, 1, 9};
  int x = 1;
  int result = search(arr, n, x);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index: " << result;
}

Algorithme de recherche linéaire pour les correspondances multiples

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
  vector<int> ans;
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      ans.push_back(i);
    }
  }
  return ans;
}

int main() {
  int n = 9;
  int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
  int x = 1;
  vector<int> res = search(arr, n, x);
  if (res.empty()) {
    cout << "Element not found!!";
  } else {
    cout << "Element found at ";
    for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
    }
  }
}

Complexité de l’algorithme de recherche linéaire

Complexité du temps

• Cas moyen

La complexité temporelle de l’algorithme de recherche linéaire est O(n).

• Meilleur cas

Le meilleur cas de complexité temporelle est O(1). Elle se produit lorsque l’élément à rechercher est le premier élément présent dans le tableau.

• Pire cas

Le pire cas se produit lorsque l’élément que nous recherchons n’est pas présent dans le tableau ou se trouve au dernier index du tableau. La complexité temporelle dans le pire des cas est O(n).

Complexité spatiale

La complexité spatiale de cet algorithme dépend du nombre de correspondances et de l’implémentation utilisée. En général, la complexité spatiale est indiquée par O(1) mais peut être plus importante si plusieurs index de correspondance sont stockés dans un tableau.