Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje