6 druhov vyhľadávacích algoritmov a ich fungovanie

Vyhľadávacie algoritmy si môžete predstaviť ako digitálnych detektívov, ktorí v rozsiahlych dátových kolekciách, ako sú rôzne weby alebo databázy, nachádzajú to, čo hľadáte, a to s čo najmenším počtom krokov.

Od Googlu a Amazonu až po Facebook a Netflix, vyhľadávacie algoritmy zohrávajú kľúčovú úlohu v digitálnych interakciách každodenného života.

V tomto článku sa dozviete o najčastejších typoch vyhľadávacích algoritmov, ich časových nárokoch, princípoch ich fungovania a reálnych aplikáciách v informatike.

Nižšia priemerná zložitosť prípadov je lepšia pre rýchlejší výkon, najmä pri rozsiahlych vstupoch. Algoritmy ako binárne vyhľadávanie O(log n) sú vysoko efektívne.

Na druhej strane, vyššie komplexity, ako napríklad O(n), sa môžu stať nepraktickými pre veľké súbory dát z kvôli rastu dĺžky trvania, ktorý je lineárny, alebo dokonca ešte vyšší ako lineárny. Efektivita však závisí aj od faktorov, ako je kontext daného problému, zdrojov a požiadavky konkrétnej aplikácie.

1. Algoritmus lineárneho vyhľadávania

Lineárne vyhľadávanie, známe aj ako sekvenčné vyhľadávanie, iteruje cez každý prvok poľa a porovnáva ho s cieľovým prvkom, kým nenájde presnú zhodu. Ak vyhľadávacia funkcia dosiahne koniec poľa bez zhody, signalizuje, že cieľový prvok sa v dátovom poli nenachádza.

Cieľovým prvkom, ktorý hľadáte, môžu byť čísla, reťazce, objekty alebo akýkoľvek iný typ dát, ktorý možno uložiť do poľa. Táto flexibilita robí z lineárneho vyhľadávania univerzálny algoritmus, ktorý možno použiť na širokú škálu typov dát.

Aby sme tento proces vyhľadávania lepšie ilustrovali, uveďme si príklad z reálneho života.

Predpokladajme, že máte neusporiadaný zoznam celých čísel predstavujúcich vek ľudí v skupine. Máte za úlohu zistiť, či sa v poli nachádza konkrétny vek, povedzme 25 rokov. V rámci lineárneho vyhľadávania by ste začali na začiatku poľa a kontrolovali by ste každý prvok, jeden po druhom, kým by ste buď nenašli vek 25, alebo by ste sa dostali na koniec poľa.

Čas dokončenia lineárneho vyhľadávacieho algoritmu je úmerný veľkosti poľa. Výpočtová zložitosť lineárneho vyhľadávania je O(n), kde n je počet prvkov v poli.

Využitie lineárneho vyhľadávania

• Jednoduché vyhľadávacie úlohy: Lineárne vyhľadávanie sa často používa na široké spektrum základných vyhľadávacích úloh, pri ktorých je súbor dát malý alebo pri ktorých nie je opodstatnená dodatočná zložitosť iných algoritmov. Napríklad vyhľadávanie v malom zozname mien alebo čísel.
• Lineárne dátové štruktúry: Lineárne vyhľadávanie je základom mnohých lineárnych dátových štruktúr, ako sú polia, zoznamy a balíčky dát. Zvyčajne sa používa na prehľadávanie týchto štruktúr s cieľom nájsť konkrétne prvky alebo vykonať operácie.
• Neusporiadané polia: Keďže lineárne vyhľadávanie kontroluje každý prvok postupne, dokáže vyhľadať prvky bez ohľadu na ich pozíciu v poli.

2. Binárny vyhľadávací algoritmus

Binárne vyhľadávanie je efektívny algoritmus používaný na nájdenie cieľovej hodnoty v zoradenom zozname. Metódou binárneho vyhľadávania opakovane rozdeľuje interval vyhľadávania na polovicu. Následne skontroluje cieľovú hodnotu voči prostrednému prvku a pokračuje do pravej alebo ľavej časti poľa. Tento proces pokračuje, kým sa cieľová hodnota nenájde, alebo kým sa vyhľadávací interval neukáže ako prázdny, pretože sa cieľová hodnota v poli nenachádza.

Ukážeme si príklad použitia binárneho vyhľadávania na nájdenie konkrétnej číselnej hodnoty.

Predstavte si, že máte pole čísel: [2,5,8,12,16,23,38,56,72,91] a chcete nájsť číslo 23.

Začnete tým, že sa pozriete na stredný prvok (koreňový uzol), ktorý má hodnotu 16. Keďže 23 je väčšie ako 16, budete sa pozerať len čísla napravo od 16. Ďalej sa pozriete na stredný prvok tejto časti, ktorým je 56. Keďže 23 je menšie ako 56, budete sa pozerať len na čísla naľavo od 56. Teraz sa opäť pozriete na stredný prvok, ktorým je 23. Našli ste hľadaný kľúč!

Čas dokončenia algoritmu binárneho vyhľadávania je O (log n), kde n je počet prvkov v poli.

Aplikácia binárneho vyhľadávania

• Vyhľadávanie v databázach: Ide o efektívny algoritmus na vyhľadávanie v databázach, pomocou ktorého možno rýchlo vyhľadať záznamy na základe indexovaných polí, ako sú ID čísla alebo kľúče.
• Vyhľadávanie prvkov v usporiadaných poliach: Binárne vyhľadávanie efektívne vyhľadáva prvky v usporiadaných poliach, čo je užitočné v aplikáciách, ako je hľadanie slova v slovníku alebo hľadanie položky v usporiadanom zozname.
• Algoritmický základ: Slúži ako základný komponent pri vývoji sofistikovaných algoritmov strojového učenia. Binárne vyhľadávanie pomáha pri trénovaní neurónových sietí a optimalizácii hyperparametrov modelu.
• Optimalizácia algoritmov: Binárne vyhľadávanie sa používa v algoritmoch vrátane stratégií typu “rozdeľuj a panuj” na efektívne riešenie problémov, ako je hľadanie odmocnín alebo lokalizácia vrcholových prvkov v poliach.
• Vyhľadávanie v stromoch: Binárne vyhľadávacie stromy (binary search trees, BST) používajú tento algoritmus na efektívne vyhľadávanie, vkladanie a odstraňovanie prvkov pri zachovaní usporiadaného poradia daného stromu.

3. Interpolačné vyhľadávanie

Ak sú hodnoty v zoradenom poli rovnomerne rozložené, interpolačné vyhľadávanie má v porovnaní s binárnym vyhľadávaním značnú výhodu. Interpolácia spočíva vo vytváraní nových dátových bodov v rozsahu známeho vyhľadávacieho priestoru.

Zatiaľ čo binárne vyhľadávanie sa vždy zameriava na stredný prvok, interpolačné vyhľadávanie upravuje svoju pozíciu vyhľadávania na základe hľadanej cieľovej hodnoty. Napríklad, ak je hľadaný kľúč bližšie ku koncu, interpolačné vyhľadávanie má tendenciu začať hľadať dáta od tohto konca.

Aby sme si to trošku priblížili – skúste si predstaviť, že hľadáte konkrétnu cenu v zozname cien rôznych položiek v obchode. Tieto ceny sú zoradené od najnižšej po najvyššiu. Namiesto toho, aby ste vždy skontrolovali polovicu zoznamu (ako pri binárnom vyhľadávaní), interpolačné vyhľadávanie odhaduje, kde zhruba by sa mohla cena nachádzať na základe jej hodnoty v porovnaní s najnižšou a najvyššou cenou. Následne tento postup opakuje, kým nenájde správnu cenu.

Čas dokončenia algoritmu interpolačného vyhľadávania je O(log log n), kde n je počet prvkov v poli.

Aplikácie interpolačného vyhľadávania

• Vyhľadávanie v databázach: Interpolačné vyhľadávanie sa bežne používa v databázach na vyhľadávanie záznamov na základe určitého kľúčového prvku.
• Vyhľadávanie vo veľkých poliach: Tento vyhľadávací algoritmus uľahčuje efektívnejšie vyhľadávanie vo veľkých usporiadaných poliach, najmä ak je rozloženie hodnôt rovnomerné. Možno ho použiť v rôznych oblastiach, napríklad pri vedeckých výpočtoch, keď je potrebné efektívne prehľadávať veľké súbory dát.
• Získavanie údajov z tabuliek symbolov: Interpolačné vyhľadávanie možno použiť v tabuľkách symbolov, kde sú kľúče spojené s hodnotami. Napríklad v programovacích jazykoch sa tabuľky symbolov používajú na ukladanie premenných, funkcií a iných identifikátorov. Interpolačné vyhľadávanie môže rýchlo vyhľadať informácie spojené s konkrétnym identifikátorom.
• Časovo citlivé úlohy: Interpolačné vyhľadávanie je vďaka svojej schopnosti rýchlo vyhľadať údaje vhodné pre časovo citlivé aplikácie.

4. Skokové vyhľadávanie

Skokové vyhľadávanie, inak známe ako blokové vyhľadávanie, je špeciálne navrhnuté pre usporiadané polia. Na rozdiel od lineárneho vyhľadávania, ktoré skúma každý prvok postupne, skokové vyhľadávanie skáče v prírastkoch pevnej veľkosti, pričom vynechá viacero prvkov, aby bolo vyhľadávanie rýchlejšie.

Ak sa cieľový prvok nachádza v zadanom rozsahu, algoritmus použije lineárne vyhľadávanie v rámci tohto bloku. Tento prístup podstatne znižuje počet operácií, čím zvyšuje efektivitu vyhľadávania.

Ukážeme si príklad algoritmu skokového vyhľadávania.

Predstavte si, že sa snažíte nájsť konkrétne číslo v dlhom zozname čísel a chcete to urobiť spôsobom, ktorý je rýchlejší ako kontrolovať čísla jedno po druhom.

1. Rozhodnite sa, koľko čísel pri každom hľadaní preskočíte: Povedzme, že preskočíte vždy 3 čísla.
2. Začnite prehľadávať zoznam a zakaždým preskočte o zvolený počet, kým nenájdete číslo rovné alebo väčšie ako to, ktoré hľadáte.
3. Po nájdení rozsahu, v ktorom by sa číslo mohlo nachádzať, vykonajte lineárne vyhľadávanie, kým nenájdete cieľové číslo.

Čas dokončenia algoritmu skokového hľadania je O(√n), kde n je počet prvkov v usporiadanom poli.

Využitie skokového vyhľadávania

• Aplikácie v jazyku JavaScript: Skokové vyhľadávanie optimalizuje proces vyhľadávania v javascriptových aplikáciách, čím zvyšuje efektivitu a odozvu.
• Vyhľadávanie v databázových systémoch: Tento algoritmus vyhľadáva záznamy na základe nejakého kľúčového prvku vo veľkých databázach.
• Vyhľadávanie dát z vizuálnych médií: Skokové vyhľadávanie efektívne vyhľadáva konkrétny snímok vo veľkom videosúbore postupovaním po pevnom počte snímok.

5. Exponenciálne vyhľadávanie

Algoritmus exponenciálneho vyhľadávania sa od skokového vyhľadávania líši spôsobom rozdelenia poľa a typom vyhľadávania použitého v rámci týchto rozdelení. Zatiaľ čo skokové vyhľadávanie rozdeľuje pole na bloky a používa lineárne vyhľadávanie, exponenciálne vyhľadávanie rozdeľuje pole pomocou exponenciálnych mocnín 2 a používa binárne vyhľadávanie.

Vyhľadávacia funkcia v podstate exponenciálne prechádza celým poľom zľava a segmentuje ho na menšie bloky pomocou druhých mocnín. Algoritmus vykonáva binárne vyhľadávanie v každom z týchto blokov, kým nenájde cieľ.

Keďže tento vyhľadávací algoritmus môže byť trochu zložitý na pochopenie, ilustrujme si jeho funkciu využitím v reálnom prípade.

Predstavte si, že máte knižnú poličku plnú kníh zoradených abecedne podľa názvu. Hľadáte konkrétnu knihu, povedzme “Harry Potter a Kameň mudrcov”. Namiesto toho, aby ste prehľadávali každú knihu po jednej, rozhodnete sa použiť exponenciálne vyhľadávanie.

Funguje to takto:

1. Počiatočný bod: Začnete prvou knihou na ľavej strane vašej poličky. Ak to nie je kniha, ktorú hľadáte, pokračujte ďalej.
2. Postupujete smerom doprava, čím sa vaše vyhľadávacie okno zdvojnásobí: Ak na jednej z týchto pozícií nájdete knihu “Harry Potter a Kameň mudrcov”, našli ste svoju knihu.
3. Zopakujte postup: Pokračujte v opakovaní postupu, pričom kým knihu nenájdete, zakaždým zdvojnásobíte rozsah hľadania.

Hoci nejde o presný spôsob využitia exponenciálneho hľadania, tento príklad pomáha demonštrovať, ako môžete rýchlo nájsť knihu bez toho, aby ste museli prechádzať každú knihu po jednej.

Čas dokončenia exponenciálneho vyhľadávacieho algoritmu je O(log n), kde n je počet prvkov v zoradenom poli.

Využitie exponenciálneho vyhľadávania

• Vyhľadávanie údajov vo veľkých usporiadaných poliach: Exponenciálne vyhľadávanie rýchlo nájde prvky vo veľkých usporiadaných poliach, ako sú napríklad zoznamy produktov, exponenciálnym rozšírením rozsahu hľadania, čo je ideálne v situáciách, keď je lineárne vyhľadávanie príliš pomalé.
• Vyhľadávanie v súborových systémoch: Tento algoritmus zlepšuje vyhľadávanie v súborových systémoch rýchlym vyhľadávaním súborov alebo adresárov v adresárových štruktúrach prostredníctvom exponenciálneho rozšírenia rozsahu vyhľadávania.

6. Ternárne vyhľadávanie

Ternárne vyhľadávanie je vyhľadávací algoritmus určený na určenie pozície cieľovej hodnoty v rámci zoradeného poľa. Na rozdiel od binárneho vyhľadávania, ktoré rozdeľuje pole na dve časti, ternárne vyhľadávanie ho rozdeľuje na tri časti. Porovnaním cieľovej hodnoty s prvkami v dvoch bodoch a rozdelením poľa na tri časti vyhľadávacia funkcia efektívne zužuje priestor vyhľadávania.

Pre ilustráciu použime ternárne vyhľadávanie na nájdenie čísla 6 v poli [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Rozdeľte oblasť hľadania:
  • Rozdeľte oblasť hľadania na tri časti nájdením dvoch deliacich bodov: Jeden bod sa bude nachádzať približne v jednej tretine zľava (povedzme 4) a druhý približne v dvoch tretinách zľava (povedzme 8).
  • Tým sa oblasť rozdelí na [1, 4], (5, 8) a [9, 10].
• Porovnajte s cieľom:
  • Skontrolujte, či sa hľadané číslo (6) rovná číslu 4 alebo 8.
  • Nie je rovné 4 ani 8, takže upravíte ukazovatele na základe toho, kde by sa mohlo nachádzať číslo 6:
    • Keďže 6 je väčšie ako 4, ale menšie ako 8, presunieme ľavý ukazovateľ na 5 a pravý na 7.
• Opakujte alebo ukončite:
  • Tento postup opakujte so zmenšeným hľadaným priestorom, kým nenájdete číslo 6 alebo kým vám nezostane žiadna ďalšia oblasť, ktorú by mohol algoritmus prehľadať.
  • Nakoniec zúžite oblasť hľadania na [6, 6] a nájdete hľadané číslo!

Čas dokončenia algoritmu ternárneho vyhľadávania je O(log3 n), kde n je počet prvkov v zoradenom poli.

Využitie ternárneho vyhľadávania

• Unimodálne funkcie: Ternárne vyhľadávanie sa uplatňuje v unimodálnych funkciách na určenie ich maximálnych alebo minimálnych hodnôt. Unimodálne funkcie sú také, ktoré majú jedinú najvyššiu hodnotu.

Záver

Aplikácie rôznych typov vyhľadávacích algoritmov sú rozsiahle a rozmanité, od vyhľadávania vo veľkých databázach a pomoci pri optimalizácii aplikácií až po slúženie ako základné stavebné kamene pre vývoj pokročilých algoritmov strojového učenia pre vyhľadávanie.

Ak budete mať na pamäti časovú a priestorovú zložitosť, možnosti a zároveň výhody a nevýhody každého zo spomenutých algoritmov, budete môcť prijímať informované rozhodnutia. Či už ide o úlohu v rámci predmetu informatika alebo o vývoj ďalšej prelomovej aplikácie, zvládnutím techník, ako je binárne vyhľadávanie, DFS, BFS a stratégia „rozdeli a panuj“, môžete naplno využiť potenciál dátových štruktúr a zvýšiť výkon vášho systému.

Ak konkrétne vytvárajte alebo hodnotíte vyhľadávanie pre internetový obchod, mechanizmy fungujú v praxi trochu inak. Pozrite sa, ako vyhľadávanie v e-commerce funguje „pod kapotou“.

Najčastejšie kladené otázky