[shabbir]

Algorithm implementation

F0 = 0, F1 = 1
Fn = Fn-1+Fn-2 for n>=2.
function fibonacci_search(item: integer; arr: sort_array)return index
is
  l : index := arr'first;-- first element of array
  u : index := arr'last;-- last element of array
  m : index := (u+l)/2;
  x,a,b : integer;
begin
  a := (Fn-3);
  b := (Fn-2)-(Fn-3); 
  discrete (f2,f1) := (Fn-2,Fn-3)
	 new (f2,f1) := (f2-f1,2*f1-f2) | (a,b)
  with i := u-l+1
	 new i=i/2loop
  loop
	if item < arr(m)then
	  m := m-f1;-- compute new position of compared element 
	  f2 := f2-f1;
	  f1 := f1-f2;
	elsif item > arr(m)then
	  m := m+f1;-- compute new position of compared element
	  x := f1;
	  f1 := f2-f1;
	  f2 := x;
	  a := f2; b := f1;
   else
	  return m;-- return index of found item
   end if;
	  i := i/2;
  end loop;
end fibonacci_search;

Courtesy : http://www.auto.tuwien.ac.at/~blieb/woop/fibsearc.html