close

Algorithme de recherche linéaire (Linear Search) en C++- Explication, exemple et code

L'algorithme de recherche linéaire est une méthode simple utilisée pour trouver un élément spécifique dans une liste. Cet algorithme fonctionne en vérifiant séquentiellement chaque élément de la liste jusqu'à ce que l'élément souhaité soit trouvé ou que la liste entière soit parcourue.

Comment ça fonctionne

  1. Commencez par le premier élément de la liste.
  2. Comparez l'élément actuel avec la valeur cible.
  3. Si l'élément courant est égal à la valeur cible, l'algorithme se termine et renvoie la position de l'élément.
  4. Si ce n'est pas le cas, continuez à parcourir les éléments restants de la liste.
  5. Si la liste entière est parcourue sans trouver l'élément cible, l'algorithme renvoie une valeur indiquant non trouvé.

Exemple

Disons que nous avons une liste d'entiers et que nous voulons trouver le nombre 34 dans la liste.

Liste : {12, 45, 67, 89, 34, 56, 23, 90}

  1. Commencez par le premier élément : 12. Pas le nombre souhaité.
  2. Passer à l'élément suivant : 45. Pas le nombre souhaité.
  3. Continuez avec les éléments restants : 67, 89, 34. L'élément 34 correspond au nombre souhaité.
  4. L'algorithme se termine et renvoie la position de 34, qui est 4.

Exemple de code en C++ 

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

Dans l'exemple donné, nous avons utilisé la linearSearch fonction pour trouver le nombre 34 dans la liste des entiers. Le résultat sera la position 34 dans la liste(les positions commencent à 0) ou -1 si le numéro n'est pas trouvé.