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:

F_{0}= 0, F_{1}= 1 F_{n}= F_{n-1}+F_{n-2}for n>=2.

1functionfibonacci_search(item: integer; arr: sort_array)returnindex2is3l : index := arr'first;-- first element of array4u : index := arr'last;-- last element of array5m : index := (u+l)/2;6x,a,b : integer;7begin8a := (Fn-3);9b := (Fn-2)-(Fn-3);10discrete(f2,f1) := (Fn-2,Fn-3)11new(f2,f1) := (f2-f1,2*f1-f2) | (a,b)12withi := u-l+113newi=i/2loop14loop15ifitem < arr(m)then16m := m-f1;-- compute new position of compared element17f2 := f2-f1;18f1 := f1-f2;19elsifitem > arr(m)then20m := m+f1;-- compute new position of compared element21x := f1;22f1 := f2-f1;23f2 := x;24a := f2; b := f1;25else26returnm;-- return index of found item27endif;28i := i/2;29endloop;30endfibonacci_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 F_{n-1} (N=F_{n-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 F_{n-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 F_{j-1} elements, the
length of the subset is bounded to F_{j-1}-1 elements.
To search through a range with a length of F_{n-1} at
the beginning we have to make n comparisons in the worst case.
F_{n}=(1/sqrt(5))*((1+sqrt(5))/2)^{n}, that's
approximately c*1,618^{n} (with a constant c).
For N+1 = c*1,618^{n} elements we need n comparisons,
i.e. the maximum number of comparisons is **O (ld N)**.

[Ott93, p. 189]

[ Samples Overview | Bibliography | WOOP Project ]