Przeszukiwanie liniowe

Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) – najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.

Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do $n,$ gdzie $n$ to całkowita liczba elementów. Algorytm ma złożoność $O(n).$

Pseudokod:

szukany_klucz := określona wartość;
znaleziony_indeks := ?;
for index := 1 to n do
   if tablica[index].klucz = szukany_klucz then
   begin
         {znaleziono element o podanym kluczu, zapamiętujemy pozycję w tablicy}
         znaleziony_indeks := index;
         break; { koniec iterowania}
   end;

Wyszukiwanie liniowe może być jedynym sposobem wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy.

Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową).

Dodatkowo jeśli wiadomo, że pewne klucze mogą być wyszukiwane częściej niż inne, można modyfikować kolejność danych, tak aby ponowne wyszukiwanie tego samego klucza kończyło się powodzeniem szybciej. Metoda ta nosi nazwę move-to-front, Donald Knuth wymienia w swojej pracy Sztuka programowania dwie strategie:

natychmiastowe przesunięcie znalezionego elementu na początek sekwencji,
przesunięcie tylko o jedną pozycję w stronę początku sekwencji.

Zobacz też[edytuj | edytuj kod]