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). +more 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í. +more 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

Kategorie:Vyhledávací algoritmy