Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / JavaScript

Linearno iskanje

Linearno iskanje preverja elemente polja po vrsti, dokler ne najde ujemanja ali ne pride do konca. Polja ni treba urediti; prikazana funkcija vrne indeks prvega ujemanja ali -1.

Različica: 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 iskanje (linear search) je algoritem, ne ključna beseda JavaScripta. Elemente preverja zaporedno od indeksa 0 in se ustavi ob prvem ujemanju. Polja ni treba urediti. linearSearch(array, target) vrne indeks ustreznega elementa ali -1, tudi pri praznem polju.

Primer uporablja ===: tipov ne pretvarja, zato se število 8 ne ujema z besedilom "8". NaN se ne ujema niti z NaN, objekti pa se ujemajo le, če gre za isti objekt. Funkcija polja ne spremeni. Primer predpostavlja običajno polje brez praznih mest, ki med iskanjem ostane nespremenjeno.

Pri n elementih je v najslabšem primeru potrebnih n primerjav: čas je O(n), dodatni pomnilnik pa O(1), če imata branje in primerjava konstanten strošek. Takojšnje ujemanje traja O(1). Rezultat preverite z index !== -1, ne z if (index): veljaven indeks 0 je v logičnem kontekstu neresničen, -1 pa resničen.

Vgrajena metoda array.indexOf(target) prav tako vrne prvi indeks s strogo primerjavo, vendar preskoči manjkajoče indeksne lastnosti; prikazana zanka jih prebere in običajno dobi undefined. Algoritem nima svoje izdaje ECMAScript; primer uporablja sintakso, ki je na voljo v ES3, in ne potrebuje Web APIs ali sodobnih metod polj.

Primeri

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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri