Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / JavaScript

Lineárne vyhľadávanie

Lineárne vyhľadávanie kontroluje prvky poľa v poradí, kým nenájde zhodu alebo nedôjde na koniec. Pole nemusí byť zoradené; uvedená funkcia vráti index prvej zhody alebo -1.

Verzia: 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;
}

Lineárne vyhľadávanie (linear search) je algoritmus, nie kľúčové slovo JavaScriptu. Kontroluje prvky postupne od indexu 0 a skončí pri prvej zhode. Pole nemusí byť zoradené. linearSearch(array, target) vráti index zodpovedajúceho prvku alebo -1, a to aj pre prázdne pole.

Príklad používa ===: nekonvertuje typy, takže číslo 8 sa nezhoduje s textom "8". NaN sa nezhoduje ani s hodnotou NaN a objekty sa zhodujú iba vtedy, keď ide o ten istý objekt. Funkcia pole nemení. Príklad predpokladá obyčajné pole bez prázdnych miest, ktoré sa počas vyhľadávania nemení.

Pre n prvkov si najhorší prípad vyžaduje n porovnaní: čas je O(n) a dodatočná pamäť O(1), za predpokladu, že čítanie a porovnávanie majú konštantnú cenu. Okamžitá zhoda trvá O(1). Výsledok kontrolujte pomocou index !== -1, nie pomocou if (index): platný index 0 je v logickom kontexte nepravdivý, kým -1 je pravdivý.

Vstavaná metóda array.indexOf(target) tiež vracia prvý index pri striktnom porovnaní, ale vynecháva chýbajúce indexové vlastnosti; uvedená slučka ich číta a zvyčajne získa undefined. Algoritmus nemá vlastné vydanie ECMAScriptu; príklad používa syntax dostupnú v ES3 a nepotrebuje Web APIs ani moderné metódy polí.

Prí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ýsledok

0
3
-1
-1

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje