Lineární vyhledávání

Lineární vyhledávání (také známé jako sekvenční vyhledávání) je vyhledávací algoritmus vhodný na nalezení určité hodnoty v seznamu.

Funguje na principu procházení všech prvků seznamu. Lineární vyhledávání má časovou složitost O(N). V případě náhodného rozložení je průměrně potřeba N/2 porovnání. Nejlepší případ nastane tehdy, když se hledaná hodnota nachází na prvním místě v seznamu, v tomto případě je potřeba pouze jedno porovnání. Nejhorší případ nastane tehdy, když se hodnota v seznamu vůbec nevyskytuje; v tom případě je potřeba N porovnání.

Výhodou lineárního vyhledávání, oproti efektivnějším algoritmům jako například binární vyhledávání, je možnost použití i na neuspořádaných seznamech.

V případě, že je potřeba vykonat na seznamu více vyhledávání, je vhodné použít efektivnější údajovou strukturu. Jedno z řešení je uspořádat seznam a použít binární vyhledávání. Další běžný postup je vybudovat hašovací tabulku a vyhledávat pomocí ní.

Implementace

Implementace lineárního vyhledávání v jazyce Python:

 def linear_search(hodnota, seznam):
     for prvek in seznam:
         if prvek == hodnota:
             return True
     return False

Funkcionální implementace v jazyce Haskell:

 linearSearch a [] = False
 linearSearch a (x:xs) | a == x    = True
                       | otherwise = linearSearch a xs