Interpolation search
PROBLEM
Given an ascending sequence of values A.1,...,A.N and target value V. Search routine should return an index of V in A. if V is present in the array, and N+1 otherwise.
ALGORITHM
We assume that the keys are numerical and they are in the array uniformly distributed. On average interpolation search will take about lglgN comparisons.
IMPLEMENTATION
Unit: internal function
Global variables: ascending sequence of numerical values A.1,...,A.N
Parameters: positive integer N, numerical value V
Returns: the index of V in A. if V is present in the array, and N+1 otherwise
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
|
CONNECTIONS
Literature
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
