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 <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
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<a[s]) k=s-1; else z=s+1;
najdi (a, ax, z, k);
}
}
void main() {
int pole[] ={10,1,3,8,10,15,16,18,20,21,22};
// ^---- 0-ty clen pola nesie pocet
// prvkov
int keyword = 10; // hladane cislo
int vysledok = najdi (pole, keyword, 1, pole[0]);
cout << "Pozicia " << vysledok;
}
}
Plošné hľadanie
V praxi sa častno stáva, že vyhľadávame v štrukturovanej databáze dát, kde prvky sú síce zoradené, ale podľa viacerých kritérií (rozmerov). Jedná sa o viacrozmerné súbory dát.
Typickým príkladom viacrozmerného poľa dát je knižnica. Pre vyhľadávaní konkrétnej knihy sa použijú dva vstupné údaje - meno autora a názov knihy.
Pri viacrozmerných súboroch dát sa z pravidla udáva hľadaný prvok pre každý rozmer takéhoto poľa. Výstupom potom sú súradnice, kde sa daný prvok nachádza. Takáto metóda hľadania sa nazýva "plošné hľadanie". Ako v prvom prípade, aj tu je predpoklad, že pole je utriedené (V prípade spomínanej knižnice predpokladáme abecedné zoradenie autorov a diel).
Plošné vyhľadávanie
Plošné hľadanie sa uskutočňuje prostredníctvom viacerých binárnych hľadaní (pre každý rozmer jedno). Ak nepredpokladáme, že súbor je utriedený, môžeme použiť pre každý rozmer aj inú metódu hľadania.