CKTIS / JavaScript
Recherche linéaire
La recherche linéaire examine les éléments d’un tableau dans l’ordre jusqu’à trouver une correspondance ou atteindre la fin. Le tableau n’a pas besoin d’être trié ; la fonction présentée renvoie l’indice de la première correspondance ou -1.
Version : ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntaxe
function linearSearch(array, target) {
for (var i = 0; i < array.length; i++) {
if (array[i] === target) return i;
}
return -1;
}La recherche linéaire (linear search) est un algorithme, pas un mot-clé JavaScript. Elle examine les éléments successivement, à partir de l’indice 0, et s’arrête à la première correspondance. Le tableau n’a pas besoin d’être trié. linearSearch(array, target) renvoie l’indice de l’élément correspondant ou -1, y compris pour un tableau vide.
L’exemple utilise === : il ne convertit pas les types, donc le nombre 8 ne correspond pas au texte "8". NaN ne correspond même pas à NaN, et les objets ne correspondent que s’il s’agit du même objet. La fonction ne modifie pas le tableau. L’exemple suppose un tableau ordinaire, sans trous, qui reste inchangé pendant la recherche.
Pour n éléments, le pire cas nécessite n comparaisons : le temps est O(n) et l’espace mémoire supplémentaire est O(1), en supposant que les lectures et les comparaisons ont un coût constant. Une correspondance immédiate prend un temps O(1). Vérifiez le résultat avec index !== -1, et non avec if (index) : l’indice valide 0 est falsy, tandis que -1 est truthy.
La méthode intégrée array.indexOf(target) renvoie elle aussi le premier indice avec une comparaison stricte, mais ignore les propriétés d’indice manquantes ; la boucle présentée les lit, ce qui donne généralement undefined. L’algorithme n’est associé à aucune édition particulière d’ECMAScript ; l’exemple utilise une syntaxe disponible dès ES3 et ne nécessite ni Web APIs ni méthodes modernes de tableau.
Exemples
function linearSearch(array, target) {
for (var i = 0; i < array.length; i++) {
if (array[i] === target) return i;
}
return -1;
}
var values = [8, 3, 8, 5];
console.log(linearSearch(values, 8));
console.log(linearSearch(values, 5));
console.log(linearSearch(values, 9));
console.log(linearSearch([], 8));Résultat
0 3 -1 -1
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.