Recherche linéaire
La recherche linéaire, c'est ce que vous faites quand vous cherchez un nom dans une liste non triée : commencer en haut et lire vers le bas jusqu'à le trouver. C'est la recherche la plus simple qui soit, elle fonctionne sur n'importe quelle liste, et pour les listes courtes, elle suffit souvent.
L'idée
Comparez la valeur cherchée à la première valeur de la liste. Si elles sont égales, arrêtez : la valeur cherchée est à la position 1. Sinon, comparez-la à la deuxième valeur, puis à la troisième, et ainsi de suite. Si la dernière valeur ne correspond pas non plus, la valeur cherchée n'est pas dans la liste. Rien ne doit être connu à l'avance sur la liste : elle n'a pas besoin d'être triée, et les valeurs peuvent être de n'importe quel type, du moment qu'on peut tester leur égalité.
Un exemple
Cherchez 4 dans 5, 1, 4, 2, 8. 5 est-il égal à 4 ? Non. Et 1 ? Non. Et 4 ? Oui : trouvé à la position 3 après 3 comparaisons. Cherchez maintenant 7 dans la même liste. Chacune des cinq valeurs est vérifiée et aucune ne correspond : après 5 comparaisons, la réponse est que 7 n'y est pas.
Combien de comparaisons
Trouver une valeur à la position k demande k comparaisons. Si la valeur cherchée a autant de chances d'être à chaque position, cela fait (n + 1)/2 comparaisons en moyenne : 20,5 pour 40 valeurs. Une valeur absente demande toujours n, car ce n'est qu'après la dernière comparaison qu'on est sûr qu'aucune valeur ne correspond. Le coût croît donc proportionnellement à la longueur de la liste, ce qui s'écrit O(n).
Les recherches plus rapides demandent de l'ordre
La recherche linéaire ne peut rien sauter, car dans une liste non triée, n'importe quelle valeur peut être n'importe où. Une fois la liste triée, une comparaison en dit plus qu'égal ou non : elle indique de quel côté se trouve la valeur cherchée. La recherche dichotomique s'en sert pour couper la liste en deux à chaque étape et demande environ log₂ n comparaisons, 6 au plus pour 40 valeurs. Mais trier prend aussi du temps : pour une liste qu'on ne parcourt qu'une fois, la recherche linéaire est souvent le meilleur choix.
Petites améliorations
Une version avec sentinelle place la valeur cherchée en fin de liste avant de chercher : la boucle n'a alors qu'à tester une correspondance, et plus la fin de la liste. Avancer une valeur d'une place, ou la mettre en tête, chaque fois qu'elle est trouvée rend les valeurs souvent cherchées moins coûteuses avec le temps. Aucune des deux ne change le pire cas de n comparaisons.
À vous d'essayer
Ouvrez l'application, choisissez une valeur dans Rechercher et appuyez sur Étape. La ligne pointillée montre la hauteur de la valeur cherchée, chaque valeur est mise en évidence pendant sa vérification puis estompée une fois écartée, et une correspondance devient verte. Cherchez une valeur absente de la liste pour voir un parcours complet, ou désactivez « Arrêter à la première correspondance » et choisissez Peu de valeurs distinctes pour trouver plusieurs correspondances.
Questions fréquemment posées
Quelle est la complexité en temps de la recherche linéaire ?
O(n) dans le pire cas et en moyenne, et O(1) dans le meilleur cas, quand la valeur cherchée est la première. Elle ne demande aucune mémoire supplémentaire.
Quelle est la différence entre recherche linéaire et recherche dichotomique ?
La recherche linéaire vérifie chaque valeur dans l'ordre et fonctionne sur n'importe quelle liste. La recherche dichotomique ne fonctionne que sur une liste triée, mais elle coupe en deux à chaque étape la partie qui peut contenir la valeur cherchée : il lui faut donc environ log₂ n comparaisons au lieu de n au plus.
La recherche linéaire exige-t-elle une liste triée ?
Non. C'est son principal avantage. Sur une liste triée, elle peut s'arrêter dès qu'elle dépasse la position où la valeur cherchée devrait être, mais elle reste plus lente que la recherche dichotomique.
Où utilise-t-on la recherche linéaire ?
Partout où les listes sont courtes ou non triées : trouver un élément dans un petit tableau, parcourir un fichier ou un flux qu'on ne peut lire que dans l'ordre, ou vérifier une condition sur chaque élément. Beaucoup de fonctions de bibliothèque, comme indexOf en JavaScript et list.index en Python, sont des recherches linéaires.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer la recherche linéaire