A possible improvement in binary search is not to use the middle element
at each step, but to guess more precisely where the key being sought falls
within the current interval of interest.This improved version is called
fibonacci search. Instead of splitting the array in the
middle, this implementation splits the array corresponding to the
fibonacci numbers, which are defined in
the following manner:
F0 = 0, F1 = 1
Fn = Fn-1+Fn-2 for n>=2.
1 function fibonacci_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 := (u+l)/2; 6 x,a,b : integer; 7 begin 8 a := (Fn-3); 9 b := (Fn-2)-(Fn-3); 10 discrete (f2,f1) := (Fn-2,Fn-3) 11 new (f2,f1) := (f2-f1,2*f1-f2) | (a,b) 12 with i := u-l+1 13 new i=i/2 loop 14 loop 15 if item < arr(m) then 16 m := m-f1; -- compute new position of compared element 17 f2 := f2-f1; 18 f1 := f1-f2; 19 elsif item > arr(m) then 20 m := m+f1; -- compute new position of compared element 21 x := f1; 22 f1 := f2-f1; 23 f2 := x; 24 a := f2; b := f1; 25 else 26 return m; -- return index of found item 27 end if; 28 i := i/2; 29 end loop; 30 end fibonacci_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. Let's assume that our array has the length Fn-1 (N=Fn-1). Now we divide the array into two subsets according to the both preceding fibonacci numbers and compare 'item' to the element at the position Fn-2. If 'item' is greater than the element, we continue in the right subset, otherwise in the left subset. In this algorithm we don't have to make a division to calculate the middle element, but we get along only with additions and subtractions. In our implementation we assumed that the fibonacci numbers are given explicitly (e.g. as constants in the frame program).
Beginning with an array containing Fj-1 elements, the length of the subset is bounded to Fj-1-1 elements. To search through a range with a length of Fn-1 at the beginning we have to make n comparisons in the worst case. Fn=(1/sqrt(5))*((1+sqrt(5))/2)n, that's approximately c*1,618n (with a constant c). For N+1 = c*1,618n elements we need n comparisons, i.e. the maximum number of comparisons is O (ld N).
[Ott93, p. 189]
[ Samples Overview | Bibliography | WOOP Project ]