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].KLIC

a dále nechť pro vyhledávaný klíč K platí:

K >= POLE[1].KLIC    a    K <= POLE[n].KLIC

Pak 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 (r

POLE[1].KLIC <= POLE[2].KLIC <= .... <= POLE[n-1].KLIC < POLE[n].KLIC

POLE[1].KLIC <= K

K < POLE[n].KLIC

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].KLIC

Je-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 Fl

Pro 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.