DICHOTOMICKÉ VYHLEDÁVÁNÍ
PROBLÉM
Je dáno vzestupně uspořádané pole A.1,...,A.N a hledaná hodnota V. Vyhledávací funkce vrací index V, jestliže se V nachází v poli A., jinak vrací N+1.
ALGORITMUS
Rozdělíme pole na dvě části; určíme ve které z nich musí hledaný prvek být; tuto část opět rozdělíme na dvě části ... (algoritmus se také nazývá vyhledávání půlením intervalu). V průměru je potřeba lgN porovnání.
IMPLEMENTACE
Jednotka: vnitřní funkce
Globální proměnné: uspořádané pole A.1,...,A.N libovolných prvků
Parametry: přirozené číslo N, libovolná hodnota V
Vrací: index prvku V v poli A. nebo číslo N+1, když V není prvkem pole.
BINARY_SEARCH: procedure expose A.
parse arg N, V
L = 1; R = N
do while L <= R
M = (L + R) % 2
if V = A.M then leave
if V < A.M then R = M - 1; else L = M + 1
end
if A.M = V then return M; else return N + 1
|
SOUVISLOSTI
