Vyhľadávanie dát je častým procesom vo všetkých informačných systémoch. Preto je veľmi dôležité navrhnúť taký vyhľadávací algoritmus, ktorý bude pre danú situáciu najvýhodnejší. Opäť platí pravidlo, že neexistuje univerzálny algoritmus, ktorý by bol vhodný pre všetky typy databáz.

V tomto článku sa budeme vyhľadávať dáta v už utriedenom súbore údajov. Utriedený súbor dát predstavuje ideálny prípad, pre ktorý sú vhodné metódy binárneho a plošného hľadania. Ako tieto metódy pracujú si ukážeme neskôr.

Snáď najjednoduchšou metódou vyhľadávanie dát by bola metóda postupného porovnávanie hľadaného prvku (keyword) so všetkými prvkami v súbore. Táto metóda nevyžaduje, aby bol súbor utriedený.

Ak predpokladáme, že súbor je utriedený, môžeme využiť metódu hľdania dát, ktorá sa nazýva "binárne hľadanie".

Binárne hľadanie

Podstatou binárneho hľadania je, že súbor dát sa myslene rozdelí na dve polovice, pričom každá z nich bude obsahovať rovnaký počet prvkov (v prípade párneho počtu). Rozdelením sa rozumie nájdenie stredného prvku - ktorý vlastne tvorí "stredovú čiaru".

Binárne hľadanie využívame aj v bežnom živote, pričom si to ani neuvedomujeme. Príkladom je napríklad hľadanie strany v nejakej rozsiahlej knihe.

V poli dát a[z] .. a[k] nájdeme stredný prvok a[s] podľa vz5ahu s = round (z/2+k/2). Pozor: nepočítame s obsahom daného prvku, ale iba s jeho indexom.

Druhým krorom je zistenie, v ktorej polovici sa hľadaný prvok nachádza. Ak využijeme predpoklad, že súbor dát je utriedený, môžeme povedať:

AX < A[s] --> prvok sa nachádza v 1. polovici rozdeleného poľa AX >= A[s] --> bude to 2. polovica

Pričom A[s] je index stredného prvku a AX je hľadaný prvok (keyword).

Tretí krok spočíva v odstránení tej polovice poľa, v ktorej sa prvok nenachádza. Zmenšením poľa sa rozumie modifikácia premenných Z a K, ktoré vlastne obsahujú hraničné indexy poľa.

if (AX < A[s]) then { k=s-1; } else { k=s+1 }

Binárne vyhľadávanie

Príklad využitia algoritmu v c++. O vyhľadávanie sa stará rekurzívna funkcia najdi, ktorá vracia index, na ktorom sa hľadaný prvok nachádza. Vstup funkcie tvorí pole, hľadaný prvok a počet prvkov poľa, ktoré sa majú prehľadať.

Na 0-tom indexe poľa sa nachádza počet "zmysluplných" prvkov tohto poľa. Samotné prvky sa nachádzajú na indexoch 1 .. n.

#include #include #include #include

int najdi (int a[], int ax, int z, int k) { int s=(int)floor (z/2+k/2); if (ax==a[s] || z>=k) { return s; } else { if (ax