TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Binární vyhledávání
Uniformní binární vyhledávání
Fibonacciho vyhledávání
Jiné metody vyhledávání v seřazeném seznamu
.
Implementujeme-li vyhledávací tabulku polem seřazeným podle velikosti klíčů položek, nabízejí se pro vyhledávání účinnější algoritmy, než je sekvenční vyhledávání. Tyto metody se poněkud podobají numerickým metodám pro hledání kořene funkce jedné proměnné, známe-li interval, v němž je právě jeden kořen. Zvlášť nápadná je podoba s metodou „půlení intervalu“. Na témže principu jsou založeny algoritmy třídy binárního vyhledávání a tzv. Fibonacciho vyhledávání, které budou blíže popsány v tomto odstavci.
1.2.1. Binární vyhledávání
Nechť pro pole implementující vyhledávací tabulku platí:
POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLICa dále nechť pro vyhledávaný klíč K platí:
K >= POLE[1].KLIC a K <= POLE[n].KLICPak princip binárního vyhledávání lze slovně popsat takto: Vyhledávaný klíč se porovná s klíčem položky, která je umístěna v polovině prohledávaného pole. Dojde-li ke shodě, končí vyhledávání úspěšně. Je-li vyhledávany klíč menší, postupuje se porovnáváním prostředního prvku v levé polovině původního pole, je-li větší v pravé polovině původního pole. Vyhledávání končí neúspěchem v případě, že prohledávaná část pole je prázdná (tzn. že její levý index je větší než pravý).
Zápis algoritmu má tvar:
l := 1; { var l:1..MAX; ukazatel levé hranice prohledávaného pole }
r := n; { var r:1..MAX; ukazatel pravé hranice prohledávaného pole }
repeat
i := (l+r) div 2;
if K < POLE[i].KLIC
then r := i–1; { hledaný klíč může být v levé polovině }
else l := i+1; { hledaný klíč může být v pravé polovině }
until (K = POLE[i].KLIC) or (rDijkstrova varianta binárního vyhldávání vychází z předpokladu, že pole může obsahovat více položek, jejichž klíče se navzájem rovnají. V případě úspěšného vyhledání se nalezne nejlevější položka ze skupiny položek se shodnými klíči, ATD tabulka sice takový předpoklad vylučuje, algoritmus však může být užitečný pro řadu aplikací.
Nechť platí:
POLE[1].KLIC <= POLE[2].KLIC <= .... <= POLE[n-1].KLIC < POLE[n].KLICa dále nechť pro vyhledávaný klíč K platí:
POLE[1].KLIC <= Ka
K < POLE[n].KLICPak algoritmus Dijkstrovy varianty buinárního vyhledávání má tvar:
<*kod> l := 1; r := n; while r <> (l+1) do begin i := (l+r) div 2; if POLE[i].KLIC < K then l := i else r := i end; SEARCH := K = POLE[i].KLIC; { if SEARCH then prvek POLE[i] je nejlevějším prvkem skupiny položek s klíčem rovným K }Zatímco u prvního algoritmu může úspěšné vyhledávání trvat kratší dobu než neúspěšné, Dijkstrova varianta má úspěšné i neúspěšné vyhledání stejně dlouhé.
1.2.2. Uniformní binární vyhledávání
Místo tří proměnných i, l a r lze použít pouze dvou: aktuální index i a odchylka m od aktuálního indexu i. Po každém neúspěšném porovnání ustavíme:
i := i+m a m := m div 2;Při návrhu tohoto algoritmu je nutné promyslet všechny detaily, aby nedošlo k nepředvídané chybě.
Nechť je dáno pole, pro jehož položky platí:
POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLICJe-li MAX sudé, pak algoritmus potřebuje prázdnou (slepou) položku s indexem 0, jejíž klíč se nastaví na hodnotu menší, než jsou všechny vyhledávané klíče. Algoritmus uniformního binárního vyhledávání má tvar:
POLE[0].KLIC := MINKLIC; { jen pro sudé MAX }
i := (n+1] div 2;
m := n div 2;
while (m <> 0) and (K <> POLE[i].KLIC) do
begin
if K < POLE[i].KLIC
then i := i – (m+1) div 2
else i := i + (m+1) div 2;
m := m div 2;
end;
SEARCH := K = POLE[i].KLIC;
{ if SEARCH then prvek POLE[i] je hledaný prvek }
Hlavní přednost této metody se může využít, je-li tabulka statická. V tom případě lze pro daný počet položek vytvořit před vyhledáváním pomocné pole odchylek DELTA a jejím použitím v cyklu vyhledávání odstranit operaci dělení, čímž se algoritmus značně zrychlí. Pro DELTA platí:
DELTA[j] = round (n/2j)Algoritmus uniformního vyhledávání využívající této výhody má tvar:
MOCNINA := 2; { var MOCNINA:POSINT }
for j := 1 to m+2 do { kde platí 2m-1 < n <= 2m }
begin
DELTA[j] := round(n/MOCNINA);
{ var DELTA:array[1..(m+2)] of POSINT }
MOCNINA := MOCNINA * 2;
end;
i := DELTA[1];
j := 2;
while (K <> POLE[i[.KLIC) and (DELTA[j] <> 0) do
begin
if K < POLE[i[.KLIC then i := i + DELTA[j]
else i := i - DELTA[j];
j := succ(j);
end;
SEARCH := K = POLE[i].KLIC;
{ if SEARCH then prvek POLE[i] je hledaným prvkem }
1.2.3. Fibonacciho vyhledávání
Existuje vzájemný vztah mezi binárním vyhledáváním v seřazeném poli a binárním stromem. Algoritmus Fibonacciho vyhledávání pracuje podobně jako binární vyhledávání. Daný interval v poli však nedělí na dvě poloviny, ale dělící bod odvozuje z Fibonacciho posloupnosti a k jeho získání stačí aditivní operace, což zvýší rychlost vyhledávání tam, kde aditivní operace jsou výrazně rychlejší než celočíselné dělení číslem 2.
V řadě metod hraje Fibonacciho posloupnost podobnou roli, jako mocninná řada dvou v obdobných metodách. K pochopení Fibonacciho vyhledávání se jen ztěží obejdeme bez Fibonacciho rozhodovacího stromu.
Fibonacciho strom řádu l má Fl+1-1 uzlů neterminálních a Fl+1 listů.
Je-li l = 0 nebo l = 1 je strom tvořen jen listem 0.
Je-li l>=2, pak kořenem stromu je uzel Fl
přitom levý podstrom je Fibonacciho strom řádu l-1
a pravý podstrom je Fibonacciho strom řádu l-2
jehož uzly mají hodnotu zvýšenou o FlPro jednoduchost budeme předpokládat, že n+1 je Fibonacciho číslo Fl+1. Pro jiné n je nutno provést potřebné počáteční úpravy. V následujícím algoritmu budeme používa funkce F(l) pro určení Fibonacciho čísla řádu.
Proměnné p a q budou mít vždy hodnoty dvou po sobě jdoucích Fibonacciho čísel.
Algoritmus Fibonacciho vyhledávání má tvar:
i := F(l);
p := F(l-1);
q := F(l-2);
TERM := false;
while (K <> POLE[i].KLIC) and (not TERM) do
if K < POLE[i].KLIC
then { hledá se v levém podstromu }
if q = 0
then TERM := true { vyhledávání končí v levém listu }
else { ustaví se nové hodnoty i,p a q pro levý podstrom }
begin i ;= i – q;
p1 := q; { pomocná proměnná p1}
q1 := p – q; { pomocná proměnná q1}
p := p1;
q := q1;
end
else { hledá se v pravém podstromu }
if p = 1 then TERM := true { vyhledávání končí v pravém listu }
else { ustaví se nové hodnoty i,p a q pro pravý podstrom }
begin i := i + q;
p := p – q;
q := q – p
end; { konec if K < POLE[i].KLIC a konec while }
SEARCH := not TERM;
{ if SEARCH then prvek POLE[i] je hledaným prvkem }
1.2.4. Jiné metody vyhledávání v seřazeném seznamu
Má-li se vyhledávat prvek v seznamu seřazeném podle velikosti klíčů jednotlivých položek, nabízejí se principiálně i jiné metody, které známe dobře z praxe při vyhledávání žádaného hesla ve slovníku, či osoby v telefonním seznamu. V tom případě lze vyhledávání usnadnit s využitím těchto principů:
a) Některé slovníky mají na straně opačné než je hřbet výřezy označené jednotlivými písmeny abecedy (tzv. „prstové indexy“), které umožňují jedním hmatem otevřít slovník na stránce, od které jsou uvedena hesla začínající na dané písmeno. Tento princip je podobný indexsekvenčnímu přístupu k seznamu (k vhodnému místu seznamu se dostaneme pomocí „indexu“ a dále postupujeme sekvenčně) a proto mu říkáme indexsekvenční vyhledávání. Tento přístup je vhodný především pro externí vyhledávání.
b) Hledáme-li ve slovníku, který není vybaven prstovými indexy, jistě nevyhledáváme tak, že bychom „půlili“ plný rozsah slovníku abychom zjistili, zda je hledané heslo v levé nebo v pravé polovině, ale dělící bod získáváme intuitivní interpolací. Víme-li, že hledaný klíč K leží mezi klíči K1 a K2 (K1 < K2), pak dělící bod hledáme v místě blízkém hodnotě (K – K1)/ (K2 - K) a mlčky předpokládáme, že rozdělení klíčů v intervalu od K1 do K2 je rovnoměrné. Tato úvaha je základem interpolačního vyhledávání.
Řada experimentů i praktické zkušenosti však ukazují, že interpolační metoda aplikovaná na seřazené pole nesníží počet porovnání tak dostatečně, aby se kompenzoval čas, potřebný navíc pro složitější určení dělícího bodu. Metoda může být poněkud úspěšnější při aplikaci na vyhledávání na vnějších paměťových zařízeních.
