La recherche linéaire expliquée simplement
Un tutoriel complet pour comprendre la recherche linéaire, suivre son fonctionnement pas à pas et l'implémenter en JavaScript.
La recherche linéaire
Introduction
La recherche linéaire est l'algorithme le plus simple pour trouver une valeur dans une liste.
Le principe est très direct : on parcourt les éléments un par un jusqu'à trouver la valeur recherchée.
C'est une excellente base pour comprendre la logique de recherche.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe de la recherche linéaire ;
- l'implémenter en JavaScript ;
- suivre son exécution étape par étape ;
- comprendre quand elle est utile ;
- comparer cette méthode à la recherche dichotomique.
1. Le problème de départ
Imaginons cette liste :
const numbers = [8, 3, 12, 5, 20];
Si vous cherchez 5, vous pouvez commencer au début et vérifier chaque élément.
C'est exactement le rôle de la recherche linéaire.
2. L'idée de la recherche linéaire
La logique est la suivante :
- regarder le premier élément ;
- comparer avec la valeur cherchée ;
- si ce n'est pas bon, passer à l'élément suivant ;
- recommencer jusqu'à trouver la valeur ou atteindre la fin.
3. Exemple pas à pas
Cherchons 5 dans la liste suivante :
[8, 3, 12, 5, 20]
Étape 1
Comparer 8 avec 5.
Ce n'est pas la bonne valeur.
Étape 2
Comparer 3 avec 5.
Ce n'est toujours pas la bonne valeur.
Étape 3
Comparer 12 avec 5.
Toujours pas.
Étape 4
Comparer 5 avec 5.
On a trouvé la valeur.
4. Version JavaScript
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}
Explication
- la boucle parcourt toute la liste ;
- dès qu'on trouve la valeur, on retourne l'index ;
- si rien n'est trouvé, on retourne
-1.
5. Exemple d'utilisation
const numbers = [8, 3, 12, 5, 20];
console.log(linearSearch(numbers, 5)); // 3
console.log(linearSearch(numbers, 99)); // -1
6. Pourquoi cet algorithme est utile
La recherche linéaire est simple et fonctionne sur n'importe quelle liste, triée ou non.
Elle est souvent utilisée quand :
- la liste est petite ;
- les données ne sont pas triées ;
- on veut une solution simple et lisible.
7. Les cas limites
Liste vide
linearSearch([], 10);
Résultat : -1
Un seul élément
linearSearch([10], 10);
Résultat : 0
Valeur absente
linearSearch([1, 2, 3], 8);
Résultat : -1
8. Recherche linéaire ou dichotomique ?
Recherche linéaire
- fonctionne sur n'importe quelle liste ;
- simple à écrire ;
- parcourt tout élément potentiel.
Recherche dichotomique
- nécessite une liste triée ;
- est plus rapide sur de grandes listes ;
- coupe la recherche en deux à chaque étape.
9. Erreurs fréquentes
Oublier le cas non trouvé
La fonction doit retourner quelque chose de clair si l'élément n'existe pas.
Comparer avec ==
Préférez === pour éviter les conversions implicites inattendues.
Ne pas parcourir toute la liste
Il faut bien vérifier chaque élément jusqu'à trouver la valeur ou atteindre la fin.
10. Résumé
La recherche linéaire est la méthode la plus simple pour trouver une valeur dans une liste.
À retenir :
- elle parcourt les éléments un par un ;
- elle fonctionne sur les listes triées ou non ;
- elle est simple mais moins efficace sur de grandes données ;
- elle constitue une base essentielle avant d'apprendre la recherche dichotomique.
Exercices
Exercice 1
Implémentez la recherche linéaire en JavaScript.
Exercice 2
Testez votre fonction avec une valeur présente et une valeur absente.
Exercice 3
Modifiez la fonction pour qu'elle retourne true ou false.
Exercice 4
Ajoutez un console.log à chaque étape pour suivre la progression.
Corrigés
Correction exercice 1
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}
Correction exercice 3
function contains(array, target) {
return linearSearch(array, target) !== -1;
}
Prochaine étape
Une fois la recherche linéaire comprise, la recherche dichotomique devient beaucoup plus simple à apprendre.