Przeszukiwanie liniowe – Wikipedia, wolna encyklopedia

Ten artykuł od 2021-03 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle n,}$ gdzie ${\displaystyle n}$ to całkowita liczba elementów. Algorytm ma złożoność ${\displaystyle 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:

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

• lista
• Move To Front – metoda kodowania danych
• tablica mieszająca
• wyszukiwanie binarne