Rozdiel medzi binárnym a lineárnym vyhľadávaním

Binárne vyhľadávanie vs lineárne vyhľadávanie

Lineárne vyhľadávanie, známe tiež ako sekvenčné vyhľadávanie, je najjednoduchším vyhľadávacím algoritmom. Vyhľadáva zadanú hodnotu v zozname kontrolou každého prvku v zozname. Binárne vyhľadávanie je tiež metóda použitá na nájdenie zadanej hodnoty v triedenom zozname. Metóda binárneho 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, až kým nenájde určený 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 rámci poskytnutej sekvencie alebo je nepravdivá, ak nie je v sekvencii. Pretože táto metóda kontroluje každú položku v zozname, kým sa nenájde určená položka, v najhoršom prípade prejde všetkými prvkami v zozname skôr, ako 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. Je to však veľmi jednoduché a ľahšie sa implementuje.

Čo je binárne vyhľadávanie?

Binárne vyhľadávanie je tiež metóda použitá na nájdenie určitej položky v zoradenom zozname. Táto metóda začína porovnaním hľadaného prvku s prvkami uprostred zoznamu. Ak porovnanie zistí, že dva prvky sú rovnaké, metóda sa zastaví a vráti polohu prvku. Ak je hľadaný prvok väčší ako stredný, spustí metódu znova pomocou iba spodnej polovice zoradeného zoznamu. Ak je hľadaný prvok menší ako stredný, spustí metódu znova pomocou iba hornej polovice zoradeného zoznamu. Ak hľadaný prvok nie je v zozname, metóda vráti jedinečnú hodnotu, ktorá to naznačuje. Metóda binárneho vyhľadávania preto 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 beží v logaritmickom čase, čo vedie k priemernému výkonu prípadu (log n).

Aký je rozdiel medzi binárnym a lineárnym vyhľadávaním?

Aj keď lineárne vyhľadávanie aj binárne vyhľadávanie sú metódami vyhľadávania, majú niekoľko rozdielov. Zatiaľ čo binárne vyhľadávanie funguje na triedených zoznamoch, vyhľadávanie linerov môže fungovať aj na netriedených zoznamoch. Zoradenie zoznamu má spravidla priemernú zložitosť n log n. lineárne vyhľadávanie je jednoduché a priamočiare implementovateľné 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 prípadov (n). Na druhej strane sa binárne vyhľadávanie považuje za efektívnejšiu metódu, ktorú by bolo možné použiť pri veľkých zoznamoch. Vykonávanie binárneho vyhľadávania by však mohlo 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..