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


Cover Contents Index Main page

last modified 1st August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic