Fibonacci Search Algorithm

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

1. go4expertModerator

Joined:
Aug 3, 2004
Messages:
306
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.

Joined:
Jul 12, 2004
Messages:
15,375
388
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. clockingNew Member

Joined:
Jun 12, 2007
Messages:
122
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 ?