Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / JavaScript

Wyszukiwanie liniowe

Wyszukiwanie liniowe sprawdza kolejne elementy tablicy, aż znajdzie dopasowanie lub dotrze do końca. Nie wymaga sortowania; pokazana funkcja zwraca indeks pierwszego dopasowania albo -1.

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

Składnia

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

Wyszukiwanie liniowe (linear search) to algorytm, a nie słowo kluczowe JavaScript. Sprawdza elementy kolejno, od indeksu 0, i kończy pracę po pierwszym dopasowaniu. Tablica nie musi być posortowana. Funkcja linearSearch(array, target) zwraca indeks znalezionego elementu albo -1, także dla pustej tablicy.

Przykład używa ===: nie konwertuje typów, więc liczba 8 nie pasuje do tekstu "8". NaN nie pasuje nawet do NaN, a obiekty pasują tylko wtedy, gdy są tym samym obiektem. Funkcja nie zmienia tablicy. Przykład zakłada zwykłą tablicę bez pustych miejsc, niezmienianą podczas wyszukiwania.

Dla n elementów najgorszy przypadek wymaga n porównań: czas wynosi O(n), a dodatkowa pamięć O(1), przy założeniu stałego kosztu odczytu i porównania. Trafienie od razu daje czas O(1). Sprawdzaj wynik przez index !== -1, nie przez if (index): poprawny indeks 0 jest fałszywy w kontekście logicznym, a -1 jest prawdziwy.

Wbudowane array.indexOf(target) również zwraca pierwszy indeks przy ścisłym porównaniu, lecz pomija brakujące właściwości indeksowe; pokazana pętla je odczytuje, zwykle otrzymując undefined. Algorytm nie ma własnej edycji ECMAScript; przykład używa składni dostępnej w ES3 i nie wymaga Web APIs ani nowoczesnych metod tablicowych.

Przykłady

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

Wynik

0
3
-1
-1

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła