Fibonacci Search

Algorithm description

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.

Algorithm implementation

 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;

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. 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).

Worst Case Performance

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).

Selected Bibliography

[Ott93, p. 189]

[ Samples Overview | Bibliography | WOOP Project ]