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.
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.
for index, value in enumerate(values):🧥 Vérifier chaque poche dans l'ordreif value == target:🔑 Les clés sont-elles ici ?return index✅ Trouvées : arrêter de chercherreturn -1❌ Toutes les poches vérifiées : introuvablesLa 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
- Commencer à l’indice 0.
- Comparer l’élément courant à la cible.
- Renvoyer son indice en cas d’égalité, sinon continuer.
- Renvoyer -1 après le dernier élément si la cible est absente.
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 valuesfait 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
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))
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.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Renvoyer -1 dans la boucle
La recherche abandonne dès le premier élément qui ne correspond pas.
for index, value in enumerate(values):
if value == target:
return index
return -1
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.
- First Negative Index Find where the first negative number appears. Facile
- Minimum d’un tableau Trouvez la plus petite valeur dans une liste. Facile