Interpolation Search


Algorithm description

Another variant of binary-search is not to use the middle element of a subset to compare to the searched item, but to guess more precisely where the key being sought falls within the current interval of interest (think of searching in a telephone directory). This improved version is called interpolation search. The new element is calculated as follows: (u,l...upper and lower bound of array 'arr')

m = round(l+(item-arr(l))/(arr(u)-arr(l))*(u-l))

Algorithm implementation

 1  function interpolation_search(item: Integer; arr: sort_array) return index 
 2  is
 3      l: index := arr'first; -- first element of array
 4      u: index := arr'last; -- last element of array
 5      m: index; 
 6  begin
 7      discrete (l,u) -- two-dimensional identifier
 8          new (l,u) :=
 9              (l,(l+ceiling(l+(item-arr(l))/(arr(u)-arr(l))*(u-l))-1)/2-1) |
10              ((ceiling(l+(item-arr(l))/(arr(u)-arr(l))*(u-l))+1+u)/2+1,u)
11      with i := u-l+1
12          new i<=i/2
13      loop
14          m := ceiling(l+(item-arr(l))/(arr(u)-arr(l))*(u-l)); -- split array into subsets
15          if item < arr(m) then
16              u := (l+m-1)/2-1; -- compute new upper bound
17          elsif item > arr(m) then
18              l := (m+1+u)/2+1; -- compute new lower bound
19          else
20              return m; -- return index of found item
21          end if;
22          i := u-l+1;
23      end loop;
24  end interpolation_search;

Notes on design

Since the present implementation of the preprocessor does not allow more than one identifier in the discrete-loop, our example is not executable at the moment. For further information about this algorithm please refer to Binary Search.

Worst Case Performance

Interpolation search uses fewer than

ldld(N)+1

comparisons, but the proof is far beyond the scope of this document. This function grows very slowly, but the advantage of few comparisons can be lost by the complexity of the arithmetical operations.

Selected Bibliography

[AHU83, p. 376] [Sed88, p. 201]


[ Samples Overview | Bibliography | WOOP Project ]