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))
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;
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.
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.
[AHU83, p. 376] [Sed88, p. 201]
[ Samples Overview | Bibliography | WOOP Project ]