Lineární vyhledávání

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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[editovat | editovat zdroj]

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