Lineárne vyhľadávanie (tiež známe ako sekvenčné vyhľadávanie) je vyhľadávací algoritmus, vhodný na vyhľadanie určitej hodnoty v zozname.
Funguje na princípe prechádzania všetkými prvkami zoznamu, až kým sa nenájde hľadaná hodnota. Lineárne vyhľadávanie má zložitosť O(N). V prípade náhodného rozloženia je v priemere potrebných N/2 porovnaní. Najlepší prípad nastane, ak sa hľadaná hodnota nachádza na prvom mieste v zozname, v tomto prípade je teda potrebné iba jedno porovnanie. Najhorší prípade je, ak sa hodnota v zozname nenachádza, v tomto prípade je potrebných N porovnaní.
Výhodou lineárneho vyhľadávania, oproti efektívnejším algoritmom ako napríklad binárne vyhľadávanie, je možnosť použitia aj na neusporiadané zoznamy.
V prípade, že je potrebné vykonať na zozname viacero vyhľadávaní, je vhodné použiť efektívnejšiu údajovú štruktúru. Jedno z riešení je usporiadať zoznam a použiť binárne vyhľadávanie. Ďalší bežný postup je vybudovať hašovaciu tabuľku a vyhľadávať pomocou nej.
Implementácie
Implementácia lineárneho vyhľadávania v jazyku Python:
def linear_search(hodnota, zoznam): for prvok in zoznam: if prvok == hodnota: return True return False
Funkcionálna implementácia v jazyku Haskell:
linearSearch a [] = False linearSearch a (x:xs) | a == x = True | otherwise = linearSearch a xs
Kategória:Vyhľadávacie algoritmy