Go4Expert - Fibonacci Search Algorithm

Go4Expert (http://www.go4expert.com/)

- Engineering Concepts (http://www.go4expert.com/forumdisplay.php?f=45)

- - Fibonacci Search Algorithm (http://www.go4expert.com/showthread.php?t=113)

Fibonacci Search Algorithm

Hello friends. I am doing survey on search algorithm and i want to know about fibonacci search algorithm .If you know about fibonacci algorithm plz reply me.

Thanks in advance

Re: Fibonacci Search Algorithm

Algorithm implementation

Code:

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

Re: Fibonacci Search Algorithm

hi, you are careful but I think it's only small algorithm.
I think that:

Code:

f[0] = f[1] = 1;

for (i = 2 ; i< n ; i++)

  f[ i ] = f[i -1] + f[i-2 ];

scanf( f[n]);

what do you think ?