Binárne vyhľadávanie vs lineárne vyhľadávanie
Najjednoduchším vyhľadávacím algoritmom je lineárne vyhľadávanie, známe tiež ako sekvenčné vyhľadávanie. Vyhľadá zadanú hodnotu v zozname kontrolou všetkých prvkov v zozname. Binárne vyhľadávanie je tiež metóda použitá na vyhľadanie konkrétnej hodnoty v zoradenom zozname. Metóda binárneho vyhľadávania znižuje počet skontrolovaných prvkov na polovicu (v každej iterácii) na polovicu, čím sa skracuje čas potrebný na nájdenie danej položky v zozname.
Čo je to lineárne vyhľadávanie?
Lineárne vyhľadávanie je najjednoduchšia metóda vyhľadávania, pri ktorej sa postupne kontroluje každý prvok v zozname, kým nenájde zadaný 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é prehľadať. Výstup je pravdivý, ak je zadaná položka v zadanej sekvencii, alebo nepravdivý, ak nie je v poradí. Pretož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šetkými prvkami v zozname, kým nená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 prehľadávaní prvkov vo veľkých zoznamoch. Ale je to veľmi jednoduché a ľahšie sa implementuje.
Čo je to binárne vyhľadávanie?
Binárne vyhľadávanie je tiež metóda použitá na vyhľadanie konkrétnej položky v triedenom 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 pozíciu prvku. Ak je hľadaný prvok väčší ako stredný prvok, metódu spustí znova, pričom použije iba spodnú polovicu zoradeného zoznamu. Ak je hľadaný prvok menší ako stredný prvok, metódu spustí znova, pričom použije iba hornú polovicu zoradeného zoznamu. Ak hľadaný prvok nie je v zozname, metóda vráti jedinečnú hodnotu, ktorá to naznačuje. Preto metóda binárneho vyhľadávania zníži počet porovnávaných prvkov na polovicu (v každej iterácii) na polovicu, v závislosti od výsledku porovnania. V dôsledku tohobinárne vyhľadávanie beží v logaritmickom čase, čo vedie k priemernému výkonu prípadu o (log n).
Aký je rozdiel medzi binárnym 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, liniové vyhľadávanie môže fungovať aj na netriedených zoznamoch. Triedenie zoznamu má zvyčajne priemernú zložitosť n log n. lineárne vyhľadávanie sa implementuje jednoducho a priamo ako binárne vyhľadávanie. Lineárne vyhľadávanie je však príliš pomalé na to, aby ho bolo možné použiť s veľkými zoznamami, a to kvôli jeho priemernému výkonu v prípade veľkých písmen. Na druhej strane sa binárne vyhľadávanie považuje za efektívnejšiu metódu, ktorú je možné použiť pri veľkých zoznamoch. Implementácia binárneho vyhľadávania by však mohla byť dosť zložitá a štúdia ukázala, že presný kód pre binárne vyhľadávanie nájdete iba v piatich z dvadsiatich kníh.
