Numérique et Sciences Informatiques > Algorithmique : Tris et Recherche > Algorithmes de Recherche > Recherche linéaire

La Recherche Linéaire : Une Introduction Simple

Comprendre le principe de la recherche linéaire (séquentielle) en algorithmique, avec des exemples et des explications claires pour les élèves de lycée. Apprenez à implémenter cet algorithme et à évaluer sa complexité.

Qu'est-ce que la Recherche Linéaire ?

La recherche linéaire, aussi appelée recherche séquentielle, est l'algorithme de recherche le plus simple. Elle consiste à parcourir un tableau (ou une liste) élément par élément, en comparant chaque élément à la valeur recherchée. Si la valeur est trouvée, l'algorithme renvoie sa position (indice) dans le tableau. Si la valeur n'est pas présente dans le tableau, l'algorithme renvoie généralement une valeur spéciale (par exemple, -1 ou null) pour indiquer l'échec de la recherche.

Comment fonctionne la Recherche Linéaire ?

Voici les étapes détaillées de l'algorithme de recherche linéaire :

  1. Initialisation: Commencer au premier élément du tableau (indice 0).
  2. Comparaison: Comparer l'élément courant à la valeur recherchée.
  3. Succès: Si l'élément courant est égal à la valeur recherchée, alors la recherche est réussie. Retourner l'indice de l'élément.
  4. Échec (partiel): Si l'élément courant n'est pas égal à la valeur recherchée, passer à l'élément suivant.
  5. Fin de Tableau: Si tous les éléments du tableau ont été parcourus sans trouver la valeur recherchée, alors la recherche échoue. Retourner une valeur indiquant l'échec (par exemple, -1).
L'algorithme se termine soit lorsqu'il trouve la valeur recherchée, soit lorsqu'il a parcouru tout le tableau.

Exemple Concret

Imaginez que vous avez un tableau d'entiers : tableau = [5, 12, 3, 8, 1, 9] et que vous recherchez la valeur 8. L'algorithme procèderait comme suit :

  1. Étape 1: Comparer tableau[0] (qui est 5) à 8. Ce n'est pas égal.
  2. Étape 2: Comparer tableau[1] (qui est 12) à 8. Ce n'est pas égal.
  3. Étape 3: Comparer tableau[2] (qui est 3) à 8. Ce n'est pas égal.
  4. Étape 4: Comparer tableau[3] (qui est 8) à 8. C'est égal !
  5. Résultat: L'algorithme renvoie l'indice 3 (la position de 8 dans le tableau).
Si vous recherchiez la valeur 4, l'algorithme parcourrait tout le tableau sans trouver 4 et renverrait -1.

Pseudo-code

Voici un exemple de pseudo-code pour la recherche linéaire : Fonction rechercheLineaire(tableau, valeurRecherchee): Pour i allant de 0 à taille(tableau) - 1 faire: Si tableau[i] est égal à valeurRecherchee alors: Retourner i // La valeur a été trouvée à l'indice i Fin Si Fin Pour Retourner -1 // La valeur n'a pas été trouvée dans le tableau Fin Fonction

Implémentation en Python

Voici un exemple d'implémentation de la recherche linéaire en Python : def recherche_lineaire(tableau, valeur_recherchee): for i in range(len(tableau)): if tableau[i] == valeur_recherchee: return i # La valeur a été trouvée à l'indice i return -1 # La valeur n'a pas été trouvée dans le tableau Exemple d'utilisation : tableau = [5, 12, 3, 8, 1, 9] valeur_a_rechercher = 8 indice = recherche_lineaire(tableau, valeur_a_rechercher) if indice != -1: print(f"La valeur {valeur_a_rechercher} a été trouvée à l'indice {indice}") else: print(f"La valeur {valeur_a_rechercher} n'a pas été trouvée dans le tableau")

Complexité de la Recherche Linéaire

La complexité de la recherche linéaire est O(n), où n est la taille du tableau. Dans le pire des cas (la valeur recherchée est la dernière du tableau, ou n'est pas présente), l'algorithme doit parcourir tous les éléments du tableau. Dans le meilleur des cas (la valeur recherchée est le premier élément), l'algorithme trouve la valeur en une seule étape. La complexité moyenne est également O(n).

Avantages et Inconvénients

  • Avantages:
    • Simple à comprendre et à implémenter.
    • Ne nécessite aucun tri préalable du tableau.
  • Inconvénients:
    • Peu performant pour les grands tableaux.
    • Complexité linéaire O(n).

Ce qu'il faut retenir

  • La recherche linéaire consiste à parcourir un tableau élément par élément pour trouver une valeur.
  • Elle est simple à implémenter mais peu efficace pour les grands tableaux.
  • Sa complexité est O(n).
  • Elle ne nécessite pas que le tableau soit trié.
  • Elle retourne l'indice de l'élément trouvé ou -1 si l'élément n'est pas présent.

← La Recherche Binaire et ses Conditions d'Application Le Tri par Insertion : Un Guide Complet →

FAQ

  • Quand utiliser la recherche linéaire ?

    La recherche linéaire est appropriée lorsque le tableau est petit ou lorsque l'on ne peut pas se permettre de trier le tableau au préalable (par exemple, si les données sont en constante évolution). Pour les grands tableaux triés, d'autres algorithmes de recherche comme la recherche binaire sont beaucoup plus efficaces.
  • La recherche linéaire fonctionne-t-elle avec des tableaux non triés ?

    Oui, la recherche linéaire fonctionne parfaitement avec des tableaux non triés. C'est d'ailleurs un de ses principaux avantages.
  • Quelle est la différence entre la recherche linéaire et la recherche binaire ?

    La recherche linéaire parcourt le tableau séquentiellement, tandis que la recherche binaire divise le tableau en deux à chaque étape. La recherche binaire nécessite que le tableau soit trié, mais elle est beaucoup plus rapide (complexité O(log n)) que la recherche linéaire (complexité O(n)) pour les grands tableaux.