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

Sequential search
Sequential search without sentinel
Binary search
Search in associative arrays
Search an array of abscissas

Literature

Sedgewick R. Algorithms

Addison-Wesley, Reading, Massachusetts, 1984