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.