FOR FREE CONTENT

Fibonacci Search

Back to Programming

Description

Fibonacci search is a searching technique that depends on the Fibonacci numbers and it is based on the divide and conquer principle. The Fibonacci numbers are generated as:

F(n+1) =F(n) + F(n-1) where F(i) is the ith Fibonacci number. F (0) =0 and F (1) =1, these are two initial values of the Fibonacci series.

First few Fibonacci numbers are:

0, 1, 1, 2, 3, 5, 8, 13, 21, ….

Now for this searching technique, we have to find the smallest Fibonacci number which is greater than or equal to n (the number of elements of the list). Let the two preceding Fibonacci numbers be F(m-1) and F(m-2)

First, the searched element will be compared with the range F(m-2), if the value matches, the position of the element will be printed. If x is lesser than the element then the third Fibonacci variable will be moved two Fibonacci down which will remove the 2/3rd of the unsearched list.

If the searched value is greater than the element, then the third Fibonacci variable will be moved one Fibonacci down which will remove 1/3rd of the unsearched value from the front.

EXAMPLE:

Suppose the lists of elements are:

Suppose the element is 100 which is to be searched.

The value of n is 7

So, the smallest Fibonacci number which is equal to or greater than 7 is 8.

F(m)=8, F(m-1) = 5 and F(m-2) = 3

First offset=-1

i= min(offset+3,n-1)

=min (-1+3, 6)

=min (2,6)

= 2

So, the value of index 2 is 64 will be compared with the searched element (100).

As 64 is lesser than 100

F(m) = 5, F(m-1) =3, F(m-2) =2 and the offset=2

Therefore,

i=min (offset+3, n-1)

= min (2+3,6)

=min (5,6)

= 5

Again, the value of index 5 is 100 which is the same as searched element 100. As the elements are matched the position of this element will be printed.

Code

ADVANTAGES:

In the case of random-access memory, this technique can reduce the searching time.
It only uses only addition and subtraction whereas, binary search requires multiplication or division operations.
The time complexity is lesser than the complexity of a binary search.

DISADVANTAGES:

Fibonacci search requires 4% more comparisons on average than binary search.

TIME COMPLEXITY:

At each step, the list is reduced by 1/3 on average.

So, the time complexity can be represented as:

$n / 3^{k} = 1$

$3^{k} = n$

$\log (3^{k}) = \log n$

$k = \log_{3} (n)$

therefore, in average case the time complexity of the Fibonacci search is O( $\log_{3} (n)$ ).

Please Login to Bookmark