Binárne vyhľadávanie vs lineárne vyhľadávanie
Lineárne vyhľadávanie, tiež známe ako sekvenčné vyhľadávanie, je najjednoduchší vyhľadávací algoritmus. Hľadá zadanú hodnotu v zozname kontrolou každého prvku v zozname. Binárne vyhľadávanie je tiež metóda používaná na nájdenie špecifikovanej hodnoty v zoradenom zozname. Binárna metóda vyhľadávania znižuje počet kontrolovaných prvkov na polovicu (v každej iterácii), čím sa skracuje čas potrebný na nájdenie danej položky v zozname.
Čo je lineárne vyhľadávanie?
Lineárne vyhľadávanie je najjednoduchšia metóda vyhľadávania, ktorá postupne kontroluje každý prvok v zozname, kým nenájde konkrétny prvok. Vstupom do metódy lineárneho vyhľadávania je sekvencia (napríklad pole, kolekcia alebo reťazec) a položka, ktorú je potrebné vyhľadať. Výstup má hodnotu true, ak je zadaná položka v rámci zadanej sekvencie, alebo hodnotu false, ak nie je v sekvencii. Keďže táto metóda kontroluje každú položku v zozname, kým sa nenájde zadaná položka, v najhoršom prípade prejde všetky prvky v zozname, kým nájde požadovaný prvok. Zložitosť lineárneho vyhľadávania je o(n). Preto sa považuje za príliš pomalý na použitie pri vyhľadávaní prvkov vo veľkých zoznamoch. Ale toto je veľmi jednoduché a ľahšie implementovateľné.
Čo je binárne vyhľadávanie?
Binárne vyhľadávanie je tiež metóda používaná na nájdenie špecifikovanej položky v zoradenom zozname. Táto metóda začína porovnaním hľadaného prvku s prvkami v strede zoznamu. Ak porovnanie určí, že dva prvky sú rovnaké, metóda sa zastaví a vráti polohu prvku. Ak je hľadaný prvok väčší ako stredný prvok, spustí metódu znova iba pomocou spodnej polovice zoradeného zoznamu. Ak je hľadaný prvok menší ako stredný prvok, spustí metódu znova iba s použitím hornej polovice zoradeného zoznamu. Ak sa hľadaný prvok nenachádza v zozname, metóda vráti jedinečnú hodnotu, ktorá to naznačuje. Preto metóda binárneho vyhľadávania znižuje počet porovnávaných prvkov na polovicu (v každej iterácii) v závislosti od výsledku porovnania. V dôsledku toho binárne vyhľadávanie prebieha v logaritmickom čase, výsledkom čoho je o(log n) priemerná výkonnosť prípadu.
Aký je rozdiel medzi binárnym vyhľadávaním a lineárnym vyhľadávaním?
Aj keď lineárne aj binárne vyhľadávanie sú metódy vyhľadávania, majú niekoľko rozdielov. Zatiaľ čo binárne vyhľadávanie funguje na triedených zoznamoch, linkové vyhľadávanie môže fungovať aj na nezoradených zoznamoch. Triedenie zoznamu má vo všeobecnosti priemernú zložitosť n log n. lineárne vyhľadávanie je jednoduché a priamočiare na implementáciu ako binárne vyhľadávanie. Lineárne vyhľadávanie je však príliš pomalé na to, aby sa dalo použiť s veľkými zoznamami kvôli jeho priemernému výkonu. Na druhej strane sa binárne vyhľadávanie považuje za efektívnejšiu metódu, ktorú možno použiť pri veľkých zoznamoch. Implementácia binárneho vyhľadávania však môže byť dosť zložitá a štúdia ukázala, že presný kód pre binárne vyhľadávanie možno nájsť iba v piatich z dvadsiatich kníh.
