Podcast o Lineárne a binárne vyhľadávanie

Kapitoly

Úvod do vyhľadávania

Kedy sa používa?

Príklad v praxi

Princíp rozdeľ a panuj

Zhrnutie a záver

Přepis

Jakub: Dobre, o tomto som teda vôbec nevedel – a myslím, že toto si musí vypočuť každý. Je to jeden z úplne najzákladnejších princípov v informatike, ale málokedy si to takto uvedomíme.

Nina: Presne tak! A pritom je to niečo, čo robíme v hlave takmer neustále. Hľadáme veci.

Jakub: Počúvate Studyfi Podcast. Dnes sa ponoríme do lineárneho vyhľadávania. Nina, čo to vlastne je?

Nina: Predstav si, že máš neusporiadanú kopu kníh a hľadáš jednu konkrétnu. Čo urobíš?

Jakub: No... asi by som ich prechádzal jednu po druhej, kým by som ju nenašiel. Alebo kým by som nezistil, že tam vôbec nie je.

Nina: A presne to je lineárne vyhľadávanie! Je to najjednoduchší vyhľadávací algoritmus. Postupne prechádzaš všetky položky v zozname, kým nenájdeš tú, ktorú hľadáš.

Jakub: Takže hlavnou výhodou je, že tie dáta... v mojom prípade knihy... nemusia byť vôbec usporiadané?

Nina: Bingo! To je jeho najväčšia sila. Funguje na akomkoľvek zozname, či už je zoradený podľa abecedy, veľkosti, alebo je to totálny chaos. Preto je taký univerzálny.

Jakub: A ako je to s rýchlosťou? Znie to tak, že pri obrovskom zozname by to mohlo trvať večne.

Nina: Máš pravdu, nie je to šprintér. Odborne hovoríme, že má časovú zložitosť O(n), kde 'n' je počet prvkov. V najhoršom prípade musíš prejsť celý zoznam.

Jakub: Dajme si príklad. Máme zoznam čísel, povedzme a hľadáme číslo 42.

Nina: Super. Algoritmus začne na začiatku. Je 15 rovné 42? Nie. Je 8 rovné 42? Nie. Takto pokračuje, až kým nenarazí na číslo 42 na piatej pozícii. Hotovo, našli sme ho v piatich krokoch.

Jakub: A keby sme hľadali číslo 99, ktoré v zozname nie je?

Nina: Potom by algoritmus prešiel všetkých sedem čísel, zistil by, že 99 tam nie je, a až potom by skončil. To je ten najhorší prípad, o ktorom som hovorila.

Jakub: Chápem. Takže je to super jednoduché, ale nie vždy najrýchlejšie. Čo nás privádza k otázke, či existuje lepší spôsob...

Jakub: Takže lineárne vyhľadávanie je síce jednoduché, ale pri veľkých dátach... dosť pomalé. Existuje niečo rýchlejšie?

Nina: Určite áno! A to nás privádza k nášmu poslednému dnešnému algoritmu: binárnemu vyhľadávaniu. Je to ako pretekárske auto oproti bicyklu.

Jakub: To znie sľubne! V čom je ten trik?

Nina: Trik, alebo skôr kľúčová podmienka, je, že dáta musia byť utriedené. Napríklad čísla od najmenšieho po najväčšie.

Jakub: Aha, takže nemôžem len tak hľadať v nejakom chaotickom zozname.

Nina: Presne tak. Princíp je "rozdeľ a panuj". Vieš, ako fungovali staré telefónne zoznamy?

Jakub: Matne si spomínam. To je tá vec, čo naši rodičia používali ako podložku pod monitor?

Nina: Presne tá! Keď si hľadal meno, nešiel si stranu po strane. Otvoril si zoznam zhruba v strede.

Jakub: A hneď som vedel, či mám listovať dopredu alebo dozadu. Vlastne som vždy odignoroval polovicu knihy.

Nina: A presne to robí binárne vyhľadávanie! Pozrieš sa na prostredný prvok. Ak to nie je on, zahodíš celú polovicu zoznamu, v ktorej hľadaný prvok byť nemôže.

Jakub: A tento postup opakujem, až kým ho nenájdem. Geniálne a oveľa rýchlejšie!

Nina: Kľúčové je si zapamätať: utriedené dáta a delenie na polovicu. To je celé tajomstvo efektivity.

Jakub: Skvelé. Takže dnes sme prešli od jednoduchého lineárneho až po super-rýchle binárne vyhľadávanie. Nina, ďakujem ti veľmi pekne za skvelé vysvetlenia.

Nina: Aj ja ďakujem za pozvanie. Bola to zábava!

Jakub: To bola aj pre nás. A ďakujeme aj vám, naši poslucháči, že ste boli s nami. Toto bol Studyfi Podcast. Majte sa!