ITERPOLAČNÍ VYHLEDÁVÁNÍ
PROBLÉM
Je dáno vzestupně uspořádané číselné 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
Interpolační vyhledávání snižuje počet porovnání v průměru na hodnotu lglgN. Ale předpokládá se, že prvky pole jsou čísla rovnoměrně rozložená v určitém intervalu.
IMPLEMENTACE
Jednotka: vnitřní funkce
Globální proměnné: uspořádané pole A.1,...,A.N čísel
Parametry: přirozené číslo N, číslo V
Vrací: index prvku V v A. nebo N+1, když V není prvkem pole A.
INTERPOLATION_SEARCH: procedure expose A.
parse arg N, V
L = 1; R = N
do while (A.R >= V) & (V > A.L)
M = L + TRUNC((V-A.L)/(A.R-A.L)*(R-L))
if V > A.M then L = M + 1
else if V < A.M then R = M - 1
else L = M
end
if A.L = V then return L; else return N + 1
|
SOUVISLOSTI
Literatura
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
