6 typů vyhledávacích algoritmů a jejich fungování

Vyhledávací algoritmy si můžete představit jako digitální detektivy, kteří v rozsáhlých sbírkách dat, jako jsou webové stránky nebo databáze, vyhledávají to, co potřebujete, s co nejmenším počtem kroků.

Od Googlu a Amazonu po Facebook a Netflix hrají vyhledávací algoritmy zásadní roli v digitálních interakcích v každodenním životě.

V tomto článku se dozvíte o nejběžnějších typech vyhledávacích algoritmů, jejich časové složitosti, o tom, jak fungují jejich vyhledávací procesy, a o jejich praktických aplikacích v informatice.

Nižší průměrná složitost případu je lepší pro rychlejší výkon, a to zejména u rozsáhlých vstupů. Vysoce efektivní jsou algoritmy jako binární vyhledávání O(log n).

Na druhou stranu se vyšší složitost, jako například O(n), může stát pro velké soubory dat nepraktickou kvůli lineárnímu nebo horšímu nárůstu doby běhu. Efektivita však závisí také na faktorech, jako jsou datové struktury, kontext problému, zdroje a požadavky aplikace.

1. Algoritmus lineárního vyhledávání

Lineární vyhledávání, známé také jako sekvenční vyhledávání, prochází každý prvek pole a porovnává ho s cílovým prvkem, dokud nenajde přesnou shodu. Pokud vyhledávací funkce dosáhne konce pole bez shody, signalizuje, že se cílový prvek v souboru dat nenachází.

Hledaným cílovým prvkem mohou být čísla, řetězce, objekty nebo jakýkoliv jiný datový typ, který lze uložit do pole. Díky této flexibilitě je lineární vyhledávání univerzálním algoritmem, který lze použít pro širokou škálu datových typů.

Pro lepší ilustraci tohoto procesu vyhledávání se podívejme na reálný příklad.

Řekněme, že máte neuspořádaný seznam celých čísel představujících věk lidí ve skupině. Máte za úkol zjistit, zda se v poli vyskytuje určitý věk, řekněme 25 let. Začnete na začátku pole a budete kontrolovat jednotlivé prvky, jeden po druhém, dokud nenajdete věk 25 nebo nedosáhnete konce pole.

Doba provádění lineárního vyhledávacího algoritmu je úměrná velikosti pole. Výpočetní složitost lineárního vyhledávání je O(n), kde n je počet prvků v poli.

Aplikace lineárního vyhledávání

• Jednoduché vyhledávací úlohy: Lineární vyhledávání se často používá pro široké spektrum základních vyhledávacích úloh, kde je soubor dat malý nebo kde není odůvodněná vyšší složitost jiných algoritmů. Jedná se například o vyhledávání v malém seznamu jmen nebo čísel.
• Lineární datové struktury: Lineární vyhledávání je základem mnoha lineárních datových struktur, jako jsou pole, seznamy a zásobníky. Obvykle se používá pro prohledávání těchto struktur za účelem nalezení konkrétních prvků nebo provedení operací.
• Neuspořádaná pole: Protože lineární vyhledávání kontroluje každý prvek postupně, může vyhledávat prvky bez ohledu na jejich pozici v poli.

2. Algoritmus binárního vyhledávání

Binární vyhledávání je efektivní algoritmus používaný k nalezení cílové hodnoty v setříděném seznamu. Binární vyhledání opakovaně rozděluje interval hledání na polovinu. Poté zkontroluje cílovou hodnotu vůči prostřednímu prvku a pokračuje do pravé nebo levé části pole. Tento proces pokračuje, dokud není nalezena cílová hodnota. Případně se vyhledávací interval ukáže jako prázdný, pokud se cílová hodnota v poli nevyskytuje.

Podívejme se na příklad použití binárního vyhledávání k nalezení konkrétní číselné hodnoty.

Představte si, že máte pole čísel: [2,5,8,12,16,23,38,56,72,91] a chcete najít číslo 23.

Nejprve se podíváte na prostřední prvek (kořenový uzel), který má hodnotu 16. Protože 23 je větší než 16, podíváte se pouze na čísla napravo od 16. Dále se podíváte na prostřední prvek této části, kterým je 56. Protože 23 je menší než 56, podíváte se pouze na čísla nalevo od 56. Nyní se opět podíváte na prostřední prvek, kterým je 23. Našli jste hledaný klíč!

Doba provádění binárního vyhledávacího algoritmu je O (log n), kde n je počet prvků v poli.

Aplikace binárního vyhledávání

• Vyhledávání v databázích: Jedná se o efektivní algoritmus pro vyhledávání v databázích, který umožňuje rychle najít záznamy na základě indexovaných polí, jako jsou ID nebo klíče.
• Vyhledávání prvků v setříděných polích: Binární vyhledávání efektivně vyhledává prvky v setříděných polích, což je užitečné v aplikacích, jako je hledání slova ve slovníku nebo hledání položky v setříděném seznamu.
• Algoritmický základ: Slouží jako základní součást při vývoji sofistikovaných algoritmů strojového učení. Binární vyhledávání pomáhá při trénování neuronových sítí a optimalizaci hyperparametrů modelu.
• Optimalizační algoritmy: Binární vyhledávání se používá v algoritmech, včetně strategií divide and conquer, k efektivnímu řešení problémů, jako je hledání odmocnin nebo vyhledávání vrcholových prvků v polích.
• Vyhledávání ve stromech: Binární vyhledávací stromy používají tento algoritmus k efektivnímu vyhledávání, vkládání a odstraňování prvků při zachování setříděného pořadí stromu.

3. Interpolační vyhledávání

Pokud jsou hodnoty v setříděném poli rovnoměrně rozloženy, nabízí interpolační vyhledávání oproti binárnímu vyhledávání výhodu. Interpolace spočívá ve vytváření nových datových bodů v rozsahu známého prostoru vyhledávání.

Zatímco binární hledání se vždy zaměřuje na prostřední prvek, interpolační hledání upravuje svou pozici hledání na základě hledané cílové hodnoty. Pokud je například hledaný prvek klíče blíže ke konci, má interpolační vyhledávání tendenci začít hledat data od tohoto konce.

Pro představu si řekněme, že hledáte konkrétní cenu v seznamu cen zboží v obchodě. Tyto ceny jsou seřazeny od nejnižší po nejvyšší. Místo toho, aby se vždy kontrolovala polovina seznamu (jako při binárním vyhledávání), interpolační vyhledávání odhaduje, kam by cena mohla spadat, na základě její hodnoty v porovnání s nejnižší a nejvyšší cenou. Tento postup pak opakujete, dokud nenajdete požadovanou cenu.

Doba provádění algoritmu interpolačního vyhledávání je O(log log n), kde n je počet prvků v poli.

Aplikace interpolačního vyhledávání

• Vyhledávání v databázích: Interpolační vyhledávání se běžně používá v databázích pro vyhledávání záznamů na základě nějakého klíčového prvku.
• Vyhledávání ve velkých polích: Tento vyhledávací algoritmus usnadňuje efektivnější vyhledávání ve velkých setříděných polích, zejména pokud je rozložení hodnot rovnoměrné. Lze ho použít v různých oblastech, jako jsou vědecké výpočty, kde je třeba efektivně prohledávat velké soubory dat.
• Vyhledávání dat z tabulek symbolů: Interpolační vyhledávání lze použít v tabulkách symbolů, kde jsou klíče spojeny s hodnotami. Například v programovacích jazycích se tabulky symbolů používají k ukládání proměnných, funkcí a dalších identifikátorů. Interpolační vyhledávání může rychle vyhledat informace spojené s konkrétním identifikátorem.
• Časově citlivé aplikace: Interpolační vyhledávání je díky své schopnosti rychle vyhledávat data vhodné pro časově citlivé aplikace.
• Hashovací tabulky: Efektivní pro vyhledávání dat v kombinaci s hashovací funkcí.

4. Skokové vyhledávání

Skokové vyhledávání, jinak známé jako blokové vyhledávání, je speciálně navrženo pro setříděná pole. Na rozdíl od lineárního prohledávání, které zkoumá každý prvek postupně, přeskakuje skokové prohledávání v pevně daných intervalech, čímž obchází více prvků a zrychluje prohledávání.

Pokud se cílový prvek nachází v zadaném rozsahu, algoritmus použije lineární vyhledávání v rámci tohoto bloku. Tento přístup podstatně snižuje počet operací a zvyšuje efektivitu vyhledávání.

Podívejme se na příklad algoritmu skokového vyhledávání.

Představte si, že se snažíte najít konkrétní číslo v dlouhém seznamu čísel a chcete to udělat rychleji než kontrolovat každé číslo postupně.

1. Rozhodněte, kolik čísel při každém hledání přeskočíte: Řekněme, že vynecháte vždy 3 čísla.
2. Začněte procházet seznam a pokaždé přeskočte o zvolený počet, dokud nenajdete číslo, které je stejné nebo větší než hledané.
3. Jakmile najdete rozsah, kde by se číslo mohlo nacházet, proveďte lineární hledání, dokud nenajdete cílové číslo.

Doba provádění algoritmu skokového vyhledávání je O(√n), kde n je počet prvků v setříděném poli.

Aplikace skokového vyhledávání

• Aplikace v jazyce JavaScript: Skokové vyhledávání optimalizuje proces vyhledávání v aplikacích jazyka JavaScript, a zvyšuje tak efektivitu a odezvu.
• Vyhledávání v databázích: Tento algoritmus vyhledává záznamy na základě nějakého klíčového prvku v rozsáhlých databázích.
• Vyhledávání dat z vizuálních médií: Skokové vyhledávání efektivně vyhledává konkrétní snímek v rozsáhlém videosouboru tak, že postupuje po pevném počtu snímků.

5. Exponenciální vyhledávání

Algoritmus exponenciálního prohledávání, známý také jako doubling nebo galloping search, se od skokového prohledávání liší způsobem rozdělení pole a typem prohledávání použitým v rámci těchto rozdělení. Zatímco skokové vyhledávání dělí pole na bloky a používá lineární vyhledávání, exponenciální vyhledávání dělí pole pomocí exponenciálních mocnin 2 a používá binární vyhledávání.

Vyhledávací funkce v podstatě exponenciálně prochází celé pole zleva a rozděluje ho na menší bloky pomocí mocnin 2. Algoritmus provádí binární vyhledávání v každém z těchto bloků, dokud nenajde cíl.

Protože tento vyhledávací algoritmus může být poněkud složitý, ukažme si jeho funkčnost na reálném příkladu.

Představte si, že máte knihovnu plnou knih seřazených abecedně podle názvu. Hledáte konkrétní knihu, řekněme „Harry Potter a kámen mudrců“. Namísto prohledávání každé knihy po jedné se rozhodnete použít exponenciální vyhledávání.

Funguje to takto:

1. Výchozí bod: Začínáte první knihou na levé straně poličky. Pokud to není kniha, kterou hledáte, pokračujte.
2. Posuňte se doprava a zdvojnásobte vyhledávací okno: Pokud na jedné z těchto pozic najdete knihu „Harry Potter a kámen mudrců“, našli jste ji.
3. Postup opakujte: Tento postup opakujete a pokaždé zdvojnásobujete rozsah, dokud knihu nenajdete.

I když se nejedná o přesnou aplikaci exponenciálního vyhledávání, na tomto příkladu je možné demonstrovat, jak rychle naleznete knihu, aniž byste museli procházet každou knihu po jedné.

Doba provádění exponenciálního vyhledávacího algoritmu je O(log n), kde n je počet prvků v setříděném poli.

Aplikace exponenciálního vyhledávání

• Vyhledávání dat ve velkých setříděných polích: Exponenciální prohledávání rychle najde prvky ve velkých setříděných polích, jako jsou například výpisy produktů, exponenciálním rozšířením rozsahu prohledávání, což je ideální pro situace, kdy je lineární prohledávání příliš pomalé.
• Prohledávání systémů souborů: Tento algoritmus zlepšuje vyhledávání v souborech rychlým nalezením souborů nebo adresářů v adresářových strukturách pomocí exponenciálního rozšíření rozsahu vyhledávání.

6. Ternární vyhledávání

Ternární vyhledávání je vyhledávací algoritmus určený k určení pozice cílové hodnoty v setříděném poli. Na rozdíl od binárního vyhledávání, které rozděluje pole na dvě části, ho ternární vyhledávání rozděluje na části tři. Porovnáním cílové hodnoty s prvky ve dvou bodech a rozdělením pole na tři části vyhledávací funkce efektivně zužuje vyhledávací prostor.

Pro ilustraci příkladu použijme ternární vyhledávání k nalezení čísla 6 v poli [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Rozdělte oblast vyhledávání:
  • Rozdělte oblast vyhledávání na tři části nalezením dvou dělících bodů: Jeden bod se nachází přibližně v jedné třetině cesty zleva (řekněme 4) a druhý přibližně ve dvou třetinách cesty zleva (řekněme 8).
  • Tím se oblast rozdělí na [1, 4], (5, 8) a [9, 10].
• Porovnejte s cílem:
  • Zkontrolujte, zda se hledané číslo (6) rovná číslu 4 nebo 8.
  • Není rovno ani 4, ani 8, takže upravíte ukazatele podle toho, kde by se mohlo nacházet číslo 6:
    • Protože je 6 větší než 4, ale menší než 8, přesuneme levý ukazatel na 5 a pravý na 7.
• Opakujte nebo ukončete:
  • Tento postup opakujte se zmenšeným prohledávaným prostorem, dokud nenajdete číslo 6 nebo dokud vám nezůstane žádná další oblast k prohledávání.
  • Nakonec zúžíte hledanou oblast na [6, 6] a najdete hledané číslo!

Doba provádění algoritmu ternárního vyhledávání je O(log3 n), kde n je počet prvků v setříděném poli.

Aplikace ternárního vyhledávání

• Unimodální funkce: Ternární hledání se používá u unimodálních funkcí k určení jejich maximálních nebo minimálních hodnot. Unimodální funkce jsou takové, které mají jedinou nejvyšší hodnotu.

Závěr

Aplikace různých typů vyhledávacích algoritmů jsou rozsáhlé a rozmanité, od prohledávání velkých databází a pomoci při optimalizaci aplikací až po sloužení jako základní stavební kameny pro vývoj pokročilých algoritmů strojového učení pro vyhledávání.

S ohledem na časovou a prostorovou složitost, možnosti a výhody i nevýhody každého z uvedených algoritmů můžete činit informovaná rozhodnutí. Ať už se jedná o úkol v rámci kurzu informatiky, nebo o vývoj další průlomové aplikace, zvládnutím technik, jako je binární vyhledávání, DFS, BFS a strategie „rozděl a panuj“, můžete plně využít potenciál datových struktur a zvýšit výkon svého systému.

Pokud konkrétně vytváříte nebo hodnotíte vyhledávání pro internetový obchod, fungují tyto mechanismy v praxi trochu jinak. Podívejte se, jak vyhledávání v e-commerce funguje „pod kapotou“.

Často kladené otázky