FIBONACCI SEARCH:
• The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.
• Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location varies depending on the location previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location.
• The typical example of non-uniform access storage is that of a magnetic tape, where the time to access a particular element is proportional to its distance from the element currently under the tape's head.
• Fibonacci search has a complexity of O(log(n)).
Algorithm:
Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If n is not a Fibonacci number, let Fm be the smallest number in F that is greater than n.
The array of Fibonacci numbers is defined where Fk+2 = Fk+1 + Fk, when k ≥ 0, F1 = 1, and F0 = 0.
To test whether an item is in the list of ordered numbers, follow these steps:
1. Set k = m.
2. If k = 0, stop. There is no match; the item is not in the array.
3. Compare the item against element in Fk−1.
4. If the item matches, stop.
5. If the item is less than entry Fk−1, discard the elements from positions Fk−1 + 1 to n. Set k = k − 1 and return to step 2.
6. If the item is greater than entry Fk−1, discard the elements from positions 1 to Fk−1. Renumber the remaining elements from 1 to Fk−2, set k = k − 2, and return to step 2.
A possible improvement in binary search is not to use the middle element at each step, but to guess more precisely where the key being sought falls within the current interval of interest.This improved version is called fibonacci search. Instead of splitting the array in the middle, this implementation splits the array corresponding to the fibonacci numbers, which are defined in the following manner:
F0 = 0, F1 = 1
Fn = Fn-1+Fn-2 for n>=2.
Algorithm implementation
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/2 loop
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;
|