CKTIS / JavaScript
Lineární vyhledávání
Lineární vyhledávání kontroluje prvky pole v pořadí, dokud nenajde shodu nebo nedojde na konec. Pole nemusí být seřazené; uvedená funkce vrací index první shody nebo -1.
Verze: 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;
}Lineární vyhledávání (linear search) je algoritmus, nikoli klíčové slovo JavaScriptu. Kontroluje prvky postupně od indexu 0 a skončí při první shodě. Pole nemusí být seřazené. linearSearch(array, target) vrátí index odpovídajícího prvku nebo -1, a to i pro prázdné pole.
Příklad používá ===: nepřevádí typy, takže číslo 8 neodpovídá textu "8". NaN neodpovídá ani hodnotě NaN a objekty si odpovídají pouze tehdy, jde-li o tentýž objekt. Funkce pole nemění. Příklad předpokládá běžné pole bez prázdných míst, které se během vyhledávání nemění.
Pro n prvků vyžaduje nejhorší případ n porovnání: čas je O(n) a dodatečná paměť O(1), pokud čtení a porovnání mají konstantní náklady. Okamžitá shoda trvá O(1). Výsledek kontrolujte pomocí index !== -1, nikoli if (index): platný index 0 je v logickém kontextu nepravdivý, zatímco -1 je pravdivý.
Vestavěná metoda array.indexOf(target) také vrací první index při striktním porovnání, ale chybějící indexové vlastnosti přeskakuje; uvedená smyčka je čte a obvykle získá undefined. Algoritmus nemá vlastní vydání ECMAScriptu; příklad používá syntaxi dostupnou v ES3 a nepotřebuje Web APIs ani moderní metody polí.
Příklady
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));Výsledek
0 3 -1 -1
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.