Wyszukiwanie liniowe

Wyszukiwanie liniowe to to, co robisz, szukając nazwiska na nieposortowanej liście: zaczynasz od góry i czytasz w dół, aż je znajdziesz. To najprostsze wyszukiwanie, jakie istnieje, działa na każdej liście, a przy krótkich listach często w zupełności wystarcza.

Słupki listy sprawdzane po kolei od początku, sprawdzone słupki wyblakłe, linia przerywana na wysokości szukanej wartości i wyróżniony pasujący słupek
Słupki listy sprawdzane po kolei od początku, sprawdzone słupki wyblakłe, linia przerywana na wysokości szukanej wartości i wyróżniony pasujący słupek

Idea

Porównaj szukaną wartość z pierwszą wartością listy. Jeśli są równe, zatrzymaj się: szukana wartość jest na pozycji 1. W przeciwnym razie porównaj ją z drugą wartością, potem z trzecią i tak dalej. Jeśli ostatnia wartość też nie pasuje, szukanej wartości nie ma na liście. Nie trzeba nic wiedzieć o liście z góry: nie musi być posortowana, a wartościami może być cokolwiek, co da się porównać pod względem równości.

Przykład

Szukaj 4 w 5, 1, 4, 2, 8. Czy 5 równa się 4? Nie. A 1? Nie. A 4? Tak: znaleziono na pozycji 3 po 3 porównaniach. Teraz szukaj 7 w tej samej liście. Każda z pięciu wartości zostaje sprawdzona i żadna nie pasuje, więc po 5 porównaniach odpowiedź brzmi: 7 nie ma na liście.

Ile porównań

Znalezienie wartości na pozycji k wymaga k porównań. Jeśli szukana wartość może być na każdej pozycji z równym prawdopodobieństwem, daje to średnio (n + 1)/2 porównań: 20,5 przy 40 wartościach. Brakująca wartość zawsze wymaga n, bo dopiero po ostatnim porównaniu wiadomo na pewno, że żadna wartość nie pasowała. Koszt rośnie więc proporcjonalnie do długości listy, co zapisuje się jako O(n).

Szybsze wyszukiwanie wymaga porządku

Wyszukiwanie liniowe nie może niczego pominąć, bo na nieposortowanej liście każda wartość może być wszędzie. Gdy lista jest posortowana, porównanie mówi więcej niż „równe albo nie”: mówi, po której stronie jest szukana wartość. Wyszukiwanie binarne wykorzystuje to, by na każdym kroku dzielić listę na pół, i potrzebuje około log₂ n porównań, najwyżej 6 przy 40 wartościach. Sortowanie też jednak kosztuje czas, więc dla listy przeszukiwanej tylko raz wyszukiwanie liniowe jest często lepszym wyborem.

Drobne usprawnienia

Wersja z wartownikiem przed wyszukiwaniem umieszcza szukaną wartość na końcu listy, więc pętla musi sprawdzać tylko trafienie, a nie także koniec listy. Przesuwanie wartości o jedną pozycję do przodu albo na sam początek za każdym razem, gdy zostanie znaleziona, sprawia, że często szukane wartości z czasem kosztują mniej. Żadne z tych usprawnień nie zmienia najgorszego przypadku, czyli n porównań.

Wypróbuj

Otwórz aplikację, wybierz wartość w polu Szukaj i naciśnij Krok. Linia przerywana pokazuje wysokość szukanej wartości, każda wartość jest wyróżniana podczas sprawdzania i blednie po wykluczeniu, a trafienie zmienia kolor na zielony. Szukaj wartości, której nie ma na liście, aby zobaczyć pełny przebieg, albo wyłącz Zatrzymaj przy pierwszym trafieniu i wybierz mało różnych wartości, aby znaleźć kilka trafień.

Często zadawane pytania

Jaka jest złożoność czasowa wyszukiwania liniowego?

O(n) w przypadku najgorszym i średnim oraz O(1) w najlepszym, gdy szukana wartość jest pierwsza. Nie wymaga dodatkowej pamięci.

Czym różni się wyszukiwanie liniowe od binarnego?

Wyszukiwanie liniowe sprawdza każdą wartość po kolei i działa na każdej liście. Wyszukiwanie binarne działa tylko na posortowanej liście, ale na każdym kroku dzieli na pół część, w której może być szukana wartość, więc potrzebuje około log₂ n porównań zamiast nawet n.

Czy wyszukiwanie liniowe wymaga posortowanej listy?

Nie. To jego główna zaleta. Na posortowanej liście może się zatrzymać, gdy tylko minie pozycję, na której byłaby szukana wartość, ale i tak jest wolniejsze od wyszukiwania binarnego.

Gdzie stosuje się wyszukiwanie liniowe?

Wszędzie tam, gdzie listy są krótkie lub nieposortowane: przy szukaniu elementu w małej tablicy, przeglądaniu pliku lub strumienia, który można czytać tylko po kolei, albo sprawdzaniu, czy każdy element spełnia warunek. Wiele funkcji bibliotecznych, takich jak indexOf w języku JavaScript i list.index w języku Python, to wyszukiwanie liniowe.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj wyszukiwanie liniowe