CKTIS / JavaScript
Lineare Suche
Die lineare Suche prüft die Elemente eines Arrays der Reihe nach, bis sie eine Übereinstimmung findet oder das Ende erreicht. Eine Sortierung ist nicht nötig; die gezeigte Funktion gibt den Index des ersten Treffers oder -1 zurück.
Version: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntax
function linearSearch(array, target) {
for (var i = 0; i < array.length; i++) {
if (array[i] === target) return i;
}
return -1;
}Die lineare Suche (linear search) ist ein Algorithmus und kein JavaScript-Schlüsselwort. Sie prüft die Elemente nacheinander ab Index 0 und endet beim ersten Treffer. Das Array muss nicht sortiert sein. linearSearch(array, target) gibt den Index des passenden Elements oder -1 zurück, auch bei einem leeren Array.
Das Beispiel verwendet ===: Dabei werden keine Typen umgewandelt, daher stimmt die Zahl 8 nicht mit dem Text "8" überein. NaN stimmt auch nicht mit NaN überein, und Objekte stimmen nur dann überein, wenn sie dasselbe Objekt sind. Die Funktion verändert das Array nicht. Das Beispiel setzt ein gewöhnliches Array ohne Lücken voraus, das während der Suche unverändert bleibt.
Bei n Elementen sind im ungünstigsten Fall n Vergleiche nötig: Die Laufzeit beträgt O(n), der zusätzliche Speicherbedarf O(1), vorausgesetzt, Lesen und Vergleichen benötigen konstante Zeit. Ein sofortiger Treffer benötigt O(1) Zeit. Prüfe das Ergebnis mit index !== -1, nicht mit if (index): Der gültige Index 0 ist im booleschen Kontext falsch, während -1 wahr ist.
Auch die eingebaute Methode array.indexOf(target) gibt bei striktem Vergleich den ersten Index zurück, überspringt aber fehlende Indexeigenschaften; die gezeigte Schleife liest sie aus und erhält dabei gewöhnlich undefined. Der Algorithmus gehört keiner bestimmten ECMAScript-Ausgabe an; das Beispiel verwendet Syntax, die es bereits in ES3 gibt, und benötigt weder Web APIs noch moderne Array-Methoden.
Beispiele
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));Ergebnis
0 3 -1 -1
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.