Podcast na Lineární a binární vyhledávání

Kapitoly

Ztracený vzoreček

Lineární vyhledávání: Metoda „Pavel“

Efektivnější cesta: Binární vyhledávání

Síla logaritmů

Kdy co použít?

Simulace v praxi

Shrnutí a rozloučení

Přepis

Matěj: Představ si studenta... říkejme mu Pavel. Má deset minut do začátku maturity z fyziky. Srdce mu buší, potí se mu ruce a zoufale listuje svými 150 stránkovými, chaoticky uspořádanými poznámkami. Někde tam, NĚKDE, je ten jeden jediný vzoreček pro výpočet hybnosti, který si nemůže vybavit. Stránku po stránce, řádek po řádku... čas běží.

Eliška: Chudák Pavel. To je noční můra každého studenta. Ten pocit bezmoci, když víš, že to tam někde je, ale prostě to nemůžeš najít.

Matěj: Přesně tak. A i když dnes nebudeme hledat vzorečky na poslední chvíli, princip zůstává stejný. Budeme se bavit o tom, jak počítače hledají data. Posloucháte Studyfi Podcast. Vítejte, Eliško.

Eliška: Ahoj Matěji, zdravím i všechny posluchače. Jsem ráda, že se podíváme na téma, které je naprosto všude kolem nás, i když si to často neuvědomujeme.

Matěj: Takže vyhledávací algoritmy. Zní to složitě, ale v podstatě je to jen návod, jak něco najít. Ten Pavlův chaotický přístup... má to v informatice nějaké jméno?

Eliška: Rozhodně! A je to ten nejzákladnější algoritmus ze všech. Říkáme mu lineární nebo sekvenční vyhledávání. Je to přesně to, co dělal Pavel – procházel poznámky jednu po druhé, od začátku až do konce.

Matěj: Takže prostě beru první položku, zkontroluju, jestli je to ona. Není? Beru druhou. Není? Beru třetí. A tak dál, dokud to nenajdu, nebo dokud nedojdu na konec seznamu.

Eliška: Přesně tak. Princip je neuvěřitelně jednoduchý. Představ si, že máš seznam čísel: pět, dvanáct, tři, osm, jedna a deset. A hledáš osmičku.

Matěj: Dobře, tak se podívám na pětku... to není ono. Pak na dvanáctku... taky ne. Pak trojka... nic. A hele, osmička! Na čtvrtém místě. Našel jsem ji.

Eliška: Bingo! A co kdybys hledal sedmičku?

Matěj: No... prošel bych pětku, dvanáctku, trojku, osmičku, jedničku i desítku. A na konci bych zjistil, že tam prostě není. Prošel bych celý seznam.

Eliška: A to je přesně ono. Velkou výhodou lineárního vyhledávání je, že data nemusí být nijak seřazená. Funguje to na jakémkoli chaosu, stejně jako v Pavlových poznámkách.

Matěj: To zní fajn. Kde je tedy háček?

Eliška: Háček je v čase. Když máš seznam o šesti číslech, je to rychlé. Ale co když máš milion položek? V nejhorším případě – když je prvek poslední nebo v seznamu vůbec není – musíš udělat milion porovnání. To je strašně neefektivní.

Matěj: Rozumím. Takže časová náročnost roste... no, lineárně s velikostí seznamu. Odborně se tomu říká časová složitost O(n), že?

Eliška: Přesně tak. 'n' je počet prvků v seznamu. Zdvojnásobíš počet prvků, zdvojnásobíš i maximální dobu hledání. Pro velké databáze je to prostě příliš pomalé.

Matěj: Takže potřebujeme chytřejší přístup. Něco, co není tak... zoufalé jako Pavlovo listování. Co kdyby měl Pavel své poznámky vzorně seřazené podle abecedy?

Eliška: Skvělá otázka! Tím jsi přesně uhodil hřebíček na hlavičku a dostáváme se k druhému, mnohem efektivnějšímu algoritmu: binárnímu vyhledávání. Ale má jednu zásadní podmínku.

Matěj: A to je?

Eliška: Data musí být seřazená. Ať už podle abecedy, podle velikosti čísel, prostě jakkoli uspořádaná. Bez toho to nefunguje.

Matěj: Dobře, dejme tomu, že máme seřazený seznam. Jak to funguje? Je to jako když hledám slovo ve slovníku?

Eliška: Přesně! To je dokonalá analogie. Když hledáš ve slovníku slovo „pes“, nezačneš u písmene A a nelistuješ stránku po stránce. Otevřeš slovník zhruba uprostřed. Třeba u písmene M.

Matěj: Jasně. A vím, že 'P' je v abecedě až za 'M', takže celou první polovinu slovníku můžu ignorovat a soustředit se jen na tu druhou.

Eliška: Přesně! A přesně tohle dělá binární vyhledávání. Podívá se na prvek uprostřed seznamu. Pokud je to ten, který hledáme, super, máme hotovo. Pokud je náš hledaný prvek menší, zahodíme celou pravou polovinu. Pokud je větší, zahodíme celou levou polovinu.

Matěj: A tenhle proces opakuju s tou zbývající částí? Zase ji rozpůlím?

Eliška: Ano. S každým krokem se ti prohledávaná oblast zmenší na polovinu. Je to strategie „rozděl a panuj“ v praxi. Po pár krocích ti zbyde jen malinká hrstka prvků, nebo rovnou ten jeden, který hledáš.

Matěj: To zní neuvěřitelně rychle. Když jsme mluvili o lineárním vyhledávání, zmínili jsme milion položek a potenciálně milion kroků. Jak je na tom binární vyhledávání?

Eliška: Připrav se na šok. Pro seznam s milionem prvků potřebuje binární vyhledávání v nejhorším případě zhruba 20 porovnání.

Matěj: Dvacet? Jakože ne dvacet tisíc, ale prostě dvacet? To je... šílené. Jak je to možné?

Eliška: Matematika! Časová složitost binárního vyhledávání je O(log n), tedy logaritmická. To v podstatě znamená, kolikrát musíš dělit číslo 'n' dvěma, než se dostaneš k jedničce. U milionu je to přibližně dvacetkrát.

Matěj: Pojďme si to ukázat na příkladu. Máme seřazený seznam: 1, 3, 5, 8, 10, 12, 15, 18, 20, 22. Deset prvků. Hledáme číslo 12.

Eliška: Dobře. Krok jedna: Seznam má 10 prvků. Prostřední prvek je na pozici 4, což je číslo 10. Naše hledaná 12 je větší než 10.

Matěj: Takže zahazujeme levou polovinu a zbyde nám: 12, 15, 18, 20, 22.

Eliška: Správně. Krok dva: Teď máme 5 prvků. Prostřední je 18. Naše 12 je menší než 18. Co teď?

Matěj: Zahodíme pravou polovinu. Zbyde nám jen 12 a 15.

Eliška: Perfektní. Krok tři: Ze dvou prvků vezmeme ten první jako střed, což je 12. A ejhle! 12 se rovná 12. Našli jsme ho na tři kroky. Lineární vyhledávání by jich potřebovalo šest.

Matěj: A kdybychom hledali číslo, které tam není, třeba sedmičku?

Eliška: Prošli bychom podobným procesem zmenšování, až by nám nakonec nezbyl žádný prvek k prohledání. V tu chvíli algoritmus ví, že sedmička v seznamu není. I to by trvalo jen pár kroků.

Matěj: Dobře, pojďme to shrnout. Máme dva hlavní hráče: lineární a binární vyhledávání. Kdy bych si měl vybrat které?

Eliška: Klíčová otázka je: „Jsou moje data seřazená?“ Pokud ano a je jich hodně, binární vyhledávání je jasná volba. Je nesrovnatelně rychlejší. Je to jako použít GPS místo toho, abyste se ptali každého člověka na ulici.

Matěj: To je dobré přirovnání. A když seřazená nejsou?

Eliška: Pak musíš použít lineární vyhledávání. Nebo... a to je důležité... musíš zvážit, jestli se ti nevyplatí data nejprve seřadit.

Matěj: A kdy se to vyplatí?

Eliška: Pokud v datech budeš vyhledávat jen jednou, je rychlejší prostě použít lineární vyhledávání na ten nesetříděný seznam. Samotné třídění totiž také zabere nějaký čas. Ale pokud víš, že v tom samém seznamu budeš hledat desetkrát, stokrát, tisíckrát... tak se rozhodně vyplatí jednou investovat čas do setřídění a pak těžit z bleskurychlého binárního vyhledávání při každém dalším dotazu.

Matěj: Dává smysl. A jaké jsou nejčastější chyby, které studenti dělají?

Eliška: Absolutní klasika je pokusit se použít binární vyhledávání na neseřazená data. To prostě nemůže fungovat a je to častá chytáková otázka v testech. Algoritmus buď nic nenajde, nebo vrátí naprostý nesmysl, protože jeho logika je založena na uspořádání.

Matěj: Tohle všechno zní teoreticky skvěle, ale nejlepší je si to asi osahat. Co by si posluchači měli vyzkoušet v nějaké interaktivní simulaci?

Eliška: Určitě! To je ten nejlepší způsob, jak to pochopit do hloubky. Zaprvé, hrajte si s velikostí seznamu. Zkuste 20 prvků a pak 20 000. Uvidíte, jak počet kroků u lineárního vyhledávání exploduje, zatímco u binárního se skoro nezmění.

Matěj: A určitě si zkusit tu chybu, o které jsi mluvila. Pustit binární vyhledávání na neseřazený seznam a sledovat, jak selže.

Eliška: Přesně. Tím si to zafixujete. Dále zkuste najít prvek úplně na začátku a úplně na konci. Uvidíte nejlepší a nejhorší případ pro lineární vyhledávání. A u binárního zkuste najít prvek přesně uprostřed – to je nejlepší případ, najde ho na první pokus!

Matěj: Vizualizace je asi taky klíčová. Vidět, jak binární vyhledávání doslova odřezává polovinu dat v každém kroku, musí být uspokojující.

Eliška: Je to ten nejlepší způsob, jak si uvědomit tu obrovskou sílu logaritmické složitosti. Uvidíte strmou čáru u O(n) a skoro plochou čáru u O(log n). Ten obrázek řekne víc než tisíc slov.

Matěj: Čas nám opět letí. Eliško, mohla bys na závěr dát našim posluchačům takový rychlý souhrn do kapsy?

Eliška: Samozřejmě. Pamatujte si dvě věci. Lineární vyhledávání: jednoduché, prochází všechno popořadě, funguje na čemkoli (i na chaotickém seznamu), ale je pomalé. Jeho složitost je O(n).

Matěj: A binární?

Eliška: Binární vyhledávání: super rychlé, půlí seznam v každém kroku, ale naprosto nezbytně vyžaduje seřazená data. Jeho složitost je O(log n). Pro velké seznamy je to rozdíl mezi sekundou a několika minutami.

Matěj: Takže pokud se chcete vyhnout osudu chudáka Pavla, třiďte si data!

Eliška: Přesně tak. V životě i v informatice!

Matěj: Skvělé. Moc ti děkuji, Eliško, za další super srozumitelný výklad. A děkujeme i vám, že jste poslouchali.

Eliška: Bylo mi potěšením. Učte se chytře!

Matěj: Přesně tak. Mějte se hezky a u dalšího dílu Studyfi Podcastu zase na slyšenou.