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


obálka obsah index hlavní

změněno 12. dubna 2018
Copyright © 2000-2018 Vladimír Zábrodský, RNDr.

mail