Recherche linéaire
Dernière mise à jour
La recherche linéaire (aussi appelée recherche séquentielle) est l'algorithme de recherche le plus simple : commencez au premier élément et comparez chacun à la cible jusqu'à trouver une correspondance ou épuiser les éléments. Elle ne fait aucune hypothèse sur les données — le tableau peut être non trié, et les éléments peuvent être n'importe quoi que l'on peut comparer par égalité.
L'animation ci-dessus met en évidence chaque comparaison à mesure que le parcours avance de gauche à droite et s'arrête dès que la cible apparaît. Sa simplicité se paie en vitesse : dans le pire cas, chaque élément est vérifié, elle s'exécute donc en O(n). Quand les données sont triées, la recherche dichotomique trouve la même réponse en O(log n) — et s'il vous faut d'abord des données triées, voyez le tri fusion.
Complexité en temps et en espace
| Cas | Complexité | Remarques |
|---|---|---|
| Meilleur cas | O(1) | Le premier élément est la cible. |
| Cas moyen | O(n) | En moyenne, la moitié des éléments est vérifiée avant un succès. |
| Pire cas | O(n) | La cible est en dernière position — ou absente. |
| Espace | O(1) | Seul l'indice courant est conservé. |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Commencez à l'indice 0, le premier élément du tableau. |
| 2 | Comparez l'élément courant à la valeur cible. |
| 3 | S'ils sont égaux, renvoyez l'indice courant — trouvé. |
| 4 | Sinon, avancez d'une position vers la droite et recommencez. |
| 5 | Si la fin du tableau est atteinte sans correspondance, la cible est absente (renvoyez -1). |
Exemple détaillé
Recherche de 5 dans [7, 3, 9, 1, 5, 8, 2] :
| Comparaison | Indice | Élément | Résultat |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — on continue le parcours. |
| 2 | 1 | 3 | 3 ≠ 5 — on continue le parcours. |
| 3 | 2 | 9 | 9 ≠ 5 — on continue le parcours. |
| 4 | 3 | 1 | 1 ≠ 5 — on continue le parcours. |
| 5 | 4 | 5 | 5 = 5 — trouvé à l'indice 4. |
Quand utiliser la recherche linéaire
| À utiliser quand | À éviter quand |
|---|---|
| Les données ne sont pas triées ou changent constamment | Les données sont triées — la recherche dichotomique est exponentiellement plus rapide |
| La collection est petite, la simplicité l'emporte | Le jeu de données est grand et cherché de façon répétée |
| Vous n'avez qu'un accès séquentiel (flux, listes chaînées) | Vous pouvez vous offrir un index ou une table de hachage pour des recherches en O(1) |
Code de Linear Search
Une implémentation propre et exécutable de Linear Search en Python, JavaScript, Java, C++, C, Pseudocode. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Linear Search en Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Code de Linear Search en JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Code de Linear Search en Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Code de Linear Search en C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Code de Linear Search en C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Code de Linear Search en Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)FAQ sur la recherche linéaire
Quelle est la complexité en temps de la recherche linéaire ?
O(n) dans les cas moyen et pire — le parcours peut devoir visiter chaque élément — et O(1) dans le meilleur cas, quand le premier élément est la cible. Elle utilise O(1) d'espace supplémentaire.La recherche linéaire a-t-elle besoin de données triées ?
Non — c'est son principal avantage. La recherche linéaire fonctionne sur des données totalement non triées car elle vérifie l'égalité de chaque élément ; l'ordre n'a jamais d'importance. La recherche dichotomique, en revanche, ne fonctionne que sur des tableaux triés.
Quand la recherche linéaire est-elle meilleure que la recherche dichotomique ?
Quand les données ne sont pas triées et ne sont cherchées qu'une seule fois (trier d'abord coûterait
O(n log n)), quand la collection est minuscule, ou quand vous n'avez qu'un accès séquentiel comme un flux ou une liste chaînée. Pour des recherches répétées sur des tableaux triés, la recherche dichotomique l'emporte.La recherche linéaire est-elle la même chose que la recherche séquentielle ?
Oui — les deux noms décrivent le même algorithme : parcourir les éléments dans l'ordre jusqu'à trouver la cible ou atteindre la fin de la collection.
Combien de comparaisons la recherche linéaire fait-elle en moyenne ?
Si la cible est présente et a la même probabilité d'être n'importe où, environ
n/2 comparaisons en moyenne ; si la cible est absente, exactement n. Cette croissance linéaire est la raison de son nom.Ressources associées
Plus de visualisations
