Wyszukiwanie liniowe

Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji

Co to jest wyszukiwanie liniowe?

Wyszukiwanie liniowe, nazywane też często wyszukiwaniem sekwencyjnym, polega na sprawdzaniu kolejnych elementów kolekcji jeden po drugim, aż do znalezienia szukanej wartości albo do końca listy.

Ten algorytm jest prosty i działa zarówno dla danych posortowanych, jak i nieposortowanych.

Jak działa?

  1. Zacznij od pierwszego elementu listy.
  2. Porównaj go z szukaną wartością.
  3. Jeśli jest równy — zwróć pozycję elementu.
  4. Jeśli nie — przejdź do następnego elementu.
  5. Jeśli dojdziesz do końca listy, oznacza to, że elementu nie znaleziono.

Przykład

Lista: [8, 3, 10, 5], szukamy 10.

Algorytm sprawdza kolejno:

  • 8 — nie pasuje
  • 3 — nie pasuje
  • 10 — znaleziono

Złożoność

W najgorszym przypadku trzeba sprawdzić wszystkie elementy, więc złożoność czasowa wynosi O(n).

Różnica względem wyszukiwania binarnego

Wyszukiwanie liniowe:

  • nie wymaga sortowania danych,
  • jest łatwe do zaimplementowania,
  • bywa wolne przy dużych zbiorach.

Wyszukiwanie binarne:

  • wymaga posortowanej listy,
  • działa szybciej dla dużych zbiorów,
  • ma złożoność O(log n).