Binárne vyhľadávanie
Základným problémom vyhľadávanie je štruktúra, v ktorej máme dáta uložené. Ak budeme mať uložené milión zamestnancov v obyčajnom poli a budeme medzi nimi chcieť nájsť zamestnancov s platom 36.597 kč, nezostane nám nič iné, než celé pole prejsť cyklom od začiatku do konca, kedy môžeme len dúfať, že cestou niekedy narazíme na hľadaný prvok. Najlepší prípad iste bude, keď hľadaný zamestnanec bude hneď na prvom indexu v poli, najhoršie bude ten, kedy tam zamestnanec vôbec nebude a my musíme prejsť celé milión prvkov dlhé polia, aby sme na to prišli. Priemerná časová zložitosť takéhoto naivného algoritmu by bola O (n), pričom n je dĺžka poľa.
Vyhľadávanie možno však výrazne urýchliť tým, keď si budeme udržiavať pole zotriedené. Algoritmus, ktorý sa používa pre vyhľadávanie prvkov v zotriedené poli, sa nazýva binárne vyhľadávanie. Binárne preto, že delí pole na dve polovice. Má nasledujúce priebeh:
- Pozrieme sa na hodnotu uprostred poľa (prostredný index nie je problém získať, keď poznáme dĺžku poľa, len ju vydelíme dvoma)
- Ak je hľadaný prvok menší, než ten, ktorý sa nachádza v prostriedku poľa, obmedzíme sa len na ľavú polovicu poľa a pravej si nebudeme všímať. Ak je väčší, obmedzíme sa na pravú polovicu poľa a nebudeme si všímať tej ľavej. Môžeme to urobiť vďaka tomu, že si sme istí, že v tejto polovici sa prvok nemôže nachádzať, pretože je na to moc veľký.
- Na zvyšnú polovicu aplikujeme to isté pravidlo, opäť sa pozrieme doprostred a zameriame sa len na jednu polovicu tejto polovice poľa (už nás teda zaujíma len 1/4 pôvodného poľa). Postup opakujeme, čím sa stále presnejšie a presnejšie približujeme k hľadanému prvku. Obvykle stačí len pár krokov k nájdeniu prvku, ktorý hľadáme.
- Končíme v tú chvíľu, kedy je v prostriedku prvok, ktorý hľadáme alebo akonáhle už nemáme čo deliť - vtedy tam hľadaný prvok nie je.
Keď sa nad algoritmom zamyslíme, zistíme, že v každom kroku zahodíme celú polovicu polia, ktorá nás vlastne nezaujíma, pretože vieme, že sa v nej hľadaný prvok nemôže nachádzať. Zložitosť bude teda O (log n), kde základom logaritmy bude 2 (pretože delíme na 2 polovice). Toto zrýchlenie je obrovské a jedná sa o najlepšiu možnú zložitosť problému vyhľadávania. Existujú síce algoritmy, ktoré môžu hľadať rýchlejšie, ale bohužiaľ je to vykúpené zlými najhoršími prípady.
Pretože nič nie je dokonalé, naskytá sa aj tu problém. Týmto problémom
je vlastnosť štruktúry polia, ktorá síce umožňuje rýchlo pristupovať k
prvkom pomocou indexu, ale ak chceme do poľa prvky pridávať alebo mazať,
musíme pole zväčšiť a prvky po jednom poposouvat, aby sme vytvorili miesto
na nový prvok, ktorý chceme vložiť niekam dovnútra. Táto operácia je
neskutočne časovo nákladná. Nesmieme zabudnúť na to, že pole si musíme
udržiavať zotriedené. Ak nejaký prvok pridáme, musíme ho vložiť na
miesto, kam patrí. Predstavte si pole veľké milión, kde novo vkladaný prvok
patrí niekam doprostred - musíme vykonať pol milióna posunov doprava a
vytvoriť uprostred voľné miesto. Niekto by mohol namietať, že by sme mohli
použiť spájať zoznam, tam sa síce vkladá v konštantnom čase, ale zase
nemôžeme rýchlo pristupovať k indexom. Riešenie bude teda niekde uprostred,
existujú totiž špeciálne štruktúry zvanej vyhľadávacie stromy, ktoré
oba problémy rieši. Ale o tom až nabudúce 
Pokiaľ chcete v poli len vyhľadávať, nič lepšie ako binárne vyhľadávanie nie je (ak nepoznáte o dátach nejakú ďalšiu vlastnosť). Ak chcete veľa vyhľadávať a občas niečo pridať alebo zašpiníte, stále sa algoritmus oplatí. Ak však potrebujete vyhľadávať a aj pole meniť, je to problém a čítajte ďalšie algoritmy v tejto sekcii.
Algoritmus binárneho vyhľadávania je možné zapísať s rekurzia aj bez rekurzia. Tradične začneme riešením bez rekurzia.
Zdrojový kód - bez rekurzia
public static int binary_search(int[] array, int item) { int left = 0; int right = array.length - 1; int center; if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah return -1; while (left <= right) { // pokud mame co delit center = (left + right) / 2; if (item == array[center]) return center; // nalezeno else if (item < array[center]) right = center - 1; // vyhodime pravou polovinu else left = center + 1; // vyhodime pravou polovinu } return -1; }
public static int binary_search(int[] array, int item) { int left = 0; int right = array.Length - 1; int center; if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah return -1; while (left <= right) { // pokud mame co delit center = (left + right) / 2; if (item == array[center]) return center; // nalezeno else if (item < array[center]) right = center - 1; // vyhodime pravou polovinu else left = center + 1; // vyhodime pravou polovinu } return -1; }
function binary_search(anarray: array of integer; item: integer): integer; var left, right, center: integer; begin left:=0; right:=length(anarray) - 1; if ((item < anarray[left]) or (item > anarray[right])) then // prvek mimo rozsah begin result:=-1; exit; end; while (left <= right) do begin // pokud mame co delit center:=(left + right) div 2; if (item = anarray[center]) then begin result:=center; // nalezeno exit; end else if (item < anarray[center]) then right:=center - 1 // vyhodime pravou polovinu else left:=center + 1; // vyhodime pravou polovinu end; result:=-1; end;
def binary_search(array, item) left = 0 right = array.length - 1 if ((item < array[left]) || (item > array[right])) # prvek mimo rozsah return -1 end while (left <= right) do # pokud mame co delit center = (left + right) / 2 if (item == array[center]) return center # nalezeno else if (item < array[center]) right = center - 1 # vyhodime pravou polovinu else left = center + 1 # vyhodime pravou polovinu end end end return -1 end
Rekurzívne riešenie je tu o niečo elegantnejšie, ale zase je vykúpené väčšia pamäťovú náročnosťou.
Zdrojový kód - s rekurziu
public static int binary_search(int[] array, int item, int left, int right) { int center; if (left > right) return -1; center = (left + right) / 2; if (item < array[center]) return binary_search(array, item, left, center - 1); // vyhodime pravou polovinu if (item > array[center]) return binary_search(array, item, center + 1, right); // vyhodime levou polovinu return center; // nalezeno }
public static int binary_search(int[] array, int item, int left, int right) { int center; if (left > right) return -1; center = (left + right) / 2; if (item < array[center]) return binary_search(array, item, left, center - 1); // vyhodime pravou polovinu if (item > array[center]) return binary_search(array, item, center + 1, right); // vyhodime levou polovinu return center; // nalezeno }
function binary_search(anarray: array of integer; item, left, right: integer): integer; var center: integer; begin if (left > right) then begin // nemame co delit result:=-1; exit; end; center:=(left + right) div 2; if (item < anarray[center]) then result:=binary_search(anarray, item, left, center - 1); // vyhodime pravou polovinu if (item > anarray[center]) then result:=binary_search(anarray, item, center + 1, right); // vyhodime levou polovinu if (item = anarray[center]) then result:=center; // nalezeno end;
def binary_search(array, item, left, right) return -1 if (left > right) center = (left + right) / 2 if (item < array[center]) return binary_search(array, item, left, center - 1) # vyhodime pravou polovinu end if (item > array[center]) return binary_search(array, item, center + 1, right) # vyhodime levou polovinu end return center; # nalezeno end
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.