Fibonacci Search Algorithm

Discussion in 'Engineering Concepts' started by go4expert, Aug 16, 2004.

  1. go4expert

    go4expert Moderator

    Joined:
    Aug 3, 2004
    Messages:
    306
    Likes Received:
    9
    Trophy Points:
    0
    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
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,341
    Likes Received:
    378
    Trophy Points:
    83
    Algorithm implementation

    Code:
    F0 = 0, F1 = 1
    Fn = Fn-1+Fn-2 for n>=2.
    [b]function[/b] fibonacci_search(item: integer; arr: sort_array)[b]return[/b] index
    [b]is[/b]
      l : index := arr'first;[i]-- first element of array[/i]
      u : index := arr'last;[i]-- last element of array[/i]
      m : index := (u+l)/2;
      x,a,b : integer;
    [b]begin[/b]
      a := (Fn-3);
      b := (Fn-2)-(Fn-3); 
    [b]  discrete[/b] (f2,f1) := (Fn-2,Fn-3)
    	 [b]new[/b] (f2,f1) := (f2-f1,2*f1-f2) | (a,b)
    [b]  with[/b] i := u-l+1
    	 [b]new[/b] i=i/2[b]loop[/b]
    [b]  loop[/b]
    	[b]if[/b] item < arr(m)[b]then[/b]
    	  m := m-f1;[i]-- compute new position of compared element[/i] 
    	  f2 := f2-f1;
    	  f1 := f1-f2;
    	[b]elsif[/b] item > arr(m)[b]then[/b]
    	  m := m+f1;[i]-- compute new position of compared element[/i]
    	  x := f1;
    	  f1 := f2-f1;
    	  f2 := x;
    	  a := f2; b := f1;
       [b]else[/b]
    	  [b]return[/b] m;[i]-- return index of found item[/i]
       [b]end[/b] [b]if[/b];
    	  i := i/2;
    [b]  end[/b] [b]loop[/b];
    [b]end[/b] fibonacci_search;
    
    Courtesy : http://www.auto.tuwien.ac.at/~blieb/woop/fibsearc.html
     
    Last edited: Aug 16, 2004
  3. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    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 ?
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice