Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / JavaScript

Linearno pretraživanje

Linearno pretraživanje provjerava elemente polja redom dok ne pronađe podudaranje ili dođe do kraja. Polje ne mora biti sortirano; prikazana funkcija vraća indeks prvog podudaranja ili -1.

Verzija: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Sintaksa

function linearSearch(array, target) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

Linearno pretraživanje (linear search) algoritam je, a ne ključna riječ JavaScripta. Provjerava elemente redom, počevši od indeksa 0, i zaustavlja se na prvom podudaranju. Polje ne mora biti sortirano. linearSearch(array, target) vraća indeks odgovarajućeg elementa ili -1, čak i za prazno polje.

Primjer upotrebljava ===: ne pretvara tipove, pa se broj 8 ne podudara s tekstom "8". NaN se ne podudara čak ni s NaN, a objekti se podudaraju samo ako je riječ o istom objektu. Funkcija ne mijenja polje. Primjer pretpostavlja obično polje bez praznina koje ostaje nepromijenjeno tijekom pretraživanja.

Za n elemenata najgori slučaj zahtijeva n usporedbi: vrijeme je O(n), a dodatna memorija O(1), uz pretpostavku da čitanje i usporedba imaju konstantan trošak. Trenutačno podudaranje traje O(1). Rezultat provjerite s index !== -1, a ne s if (index): valjani indeks 0 u logičkom je kontekstu falsy, dok je -1 truthy.

Ugrađena metoda array.indexOf(target) također vraća prvi indeks uz strogu usporedbu, ali preskače nedostajuća indeksna svojstva; prikazana ih petlja čita i obično dobiva undefined. Algoritam nema vlastito izdanje ECMAScripta; primjer upotrebljava sintaksu dostupnu u ES3 i ne zahtijeva Web APIs ni moderne metode polja.

Primjeri

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));

Rezultat

0
3
-1
-1

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori