1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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:
    7
    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,292
    Likes Received:
    365
    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