Lineárne vyhľadávanie

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