Lineární vyhledávání

jednoduchý způsob vyhledávání, při kterém je za účelem nalezení hledaného prvku prohledávána sekvenčně celá množina prvků

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

editovat

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