Algorithmes Python

La recherche linéaire (linear search) en Python

Dans cette leçon, vous allez implémenter la recherche linéaire pour trouver la position d'une valeur dans une liste.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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

Le problème

Parfois, les données ne sont pas triées, ou on n'y cherche qu'une fois : une courte liste de noms, les commandes du jour, la première erreur d'un journal. Il vous faut alors la recherche la plus simple, celle qui marche toujours.

Imaginez-le ainsi

La recherche linéaire, c'est comme chercher ses clés dans une rangée de poches de manteaux. Vous vérifiez la première poche, puis la suivante, une par une, et vous vous arrêtez dès que vous les trouvez. Si vous arrivez au bout de la rangée sans rien trouver, c'est que les clés n'y sont pas.

Des poches à vérifier au code
for index, value in enumerate(values):🧥 Vérifier chaque poche dans l'ordre
if value == target:🔑 Les clés sont-elles ici ?
return index✅ Trouvées : arrêter de chercher
return -1❌ Toutes les poches vérifiées : introuvables
Vérifiez un élément à la fois et arrêtez-vous au premier qui correspond.
En une phrase

La recherche linéaire vérifie les éléments d'une collection l'un après l'autre jusqu'à trouver la cible. Elle peut demander jusqu'à O(n) étapes, mais n'a pas besoin que les données soient triées.

La recherche linéaire examine chaque élément depuis le début jusqu’à trouver la cible ou atteindre la fin. Les données n’ont pas besoin d’être triées.

Fonctionnement de l’algorithme

  1. Commencer à l’indice 0.
  2. Comparer l’élément courant à la cible.
  3. Renvoyer son indice en cas d’égalité, sinon continuer.
  4. Renvoyer -1 après le dernier élément si la cible est absente.
Complexité : O(n) en temps dans les cas moyen et défavorable, avec O(1) d’espace supplémentaire.

Quand l’utiliser ?

  • Les collections non triées ou petites.
  • Chercher une seule fois, quand trier d'abord coûterait plus cher.
  • Trouver le premier élément qui remplit une condition, pas seulement une valeur exacte.

Quand s'en passer

  • De nombreuses recherches dans le même gros volume de données : triez-les une fois et utilisez la recherche dichotomique, ou construisez un set ou un dictionnaire.
  • Tester seulement la présence d'une valeur : target in values fait la même chose avec moins de code.

Visualisation de La recherche linéaire (linear search) en Python

O(n)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Code d’exemple

Exécuter le code →
main.py
def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

print(linear_search([14, 3, 27, 8, 19], 8))
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

3

Explication du code

La fonction enumerate() fournit la position et la valeur de chaque élément. Dès que la valeur cherchée apparaît, la fonction renvoie sa position, ici 3. Si elle parcourt toute la liste sans la trouver, elle renvoie -1. Dans le pire des cas, l'algorithme examine tous les éléments, sa complexité est donc O(n).

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Renvoyer -1 dans la boucle

La recherche abandonne dès le premier élément qui ne correspond pas.

Problème
for index, value in enumerate(values):
    if value == target:
        return index
    return -1
Correction
for index, value in enumerate(values):
    if value == target:
        return index
return -1

Leçon terminée ?

Marquez-la comme apprise pour suivre votre progression.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis