Fibonacci Search Algorithm

The Fibonacci search algorithm is another variant of binary search based on divide and conquer technique. The binary search as you may have learned earlier that split the array to be searched, exactly in the middle recursively to search for the key. Fibonacci search on the other hand is bit unusual and uses the Fibonacci sequence or numbers to make a decision tree and search the key.

Like binary search, the Fibonacci search also work on sorted array ( non-decreasing order).

The Fibonacci Sequence

Simply said the Fibonacci sequence is a set of numbers where any term F_n is equal to the sum of previous two terms.

F_{n} = F_{n-1} + F_{n-2}

If we try to generate first few terms of a Fibonacci sequence then we get the following numbers.

F_{0} = 0
F_{1} = 1
F_{2} = F_{1} + F_{0} = 1 + 0 = 1
F_{3} = F_{2} + F_{1} = 1 + 1 = 2
F_{4} = F_{3} + F_{2} = 2 + 1 = 3
F_{5} = F_{4} + F_{3} = 3 + 2 = 5
F_{6} = F_{5} + F_{4} = 5 + 3 = 8
F_{7} = F_{6} + F_{5} = 8 + 5 = 13
F_{8} = F_{7} + F_{6} = 13 + 8 = 21

Therefore, the Fibonacci sequence is as follows
0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...

Fibonacci Search

Algorithm Fibonacci_Search(A, n, key)
{
     low:= 0
     high:= n - 1
     loc:= -1
     flag:= 0
     while(flag != 1 && low <= high)
     { 
          // get the fibonacci f[m-1] < n
          index:=get_fibonacci(n)         
          if ( key == A[index + low]) then
           {
               flag:= 1
               loc:= index
               break
           }
          else if ( key > A[index + low] ) then
            {
              //adjust the low
               low:= low + index + 1
            }
          else
           {
               //adjust the high
               high:= low + index - 1
           }
    //adjust the n
          n:= high - low + 1
      } // end of while

//return success or not
if ( flag = 1) then
{
    return (loc + first + 1 )
}
else
{
   return -1
}

} //end 
Algorithm Fibonacci(n)
{
  fibk2:= 0
  fibk1:= 1
  fibk:= 0
    if ( n = 0 || n = 1) then
        return 0
    while ( fibk <n)
    { 
               fibk:= fibk2 + fibk1
               fibk2:= fibk1
               fibk1:= fibk
    }
     return fibk2;
}

How Fibonacci Search Works ?

Fibonacci search uses the Fibonacci numbers to create a search tree. These are the steps taken during Fibonacci search.

Step 1:

The first step is to find a Fibonacci number that is greater than or equal to the size of the array in which we are searching for the key.

Suppose the size of the array is n and fibonacci number is F_{k}.
We must find a F_{k} such that 
F_{k} \geq n

if n = 10 then we must find a F_{k} \geq n.
The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, ...
Therefore, F_{k} = 13 because 13 \geq 10.

Step 2:

The next step is to compare the key with the element at Fibonacci number F_{k-1}.

We know that F_{k} = 13 because 13 \geq 10. We must find the F_{k-1} . 
Once again we look at the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, .... 
Since, 
F_{k} = F_{k-1} + F_{k-2}
13 = 8 + 5
F_{k-1} = 8 

Step 3:

If the key and array element at F_{k-1} are equal then the key is at F_{k-1} + 1.

For example, we are searching within an array of 10 elements. 
10\hspace{3ex}34\hspace{3ex}39\hspace{3ex}45\hspace{3ex}53\hspace{3ex}58\hspace{3ex}66\hspace{3ex}75\hspace{3ex}83\hspace{3ex}88 
A[0] A[1] A[2]  A[3]  A[4]  A[5]  A[6] A[7] A[8] A[9] 

n = 10 and F_{k} = 13
Let key = 83 and F_{k-1} = 8
Therefore, key == A[8] is true.
Then the key is found at F_{k-1} + 1 which is 8 + 1 = 9^{th} position.

Step 4:

If the key is less than array element at F_{k-1}, then search the left sub-tree to F_{k-1}.

For example, we are searching within an array of 10 elements. 
10\hspace{3ex}34\hspace{3ex}39\hspace{3ex}45\hspace{3ex}53\hspace{3ex}58\hspace{3ex}66\hspace{3ex}75\hspace{3ex}83\hspace{3ex}88 
A[0] A[1] A[2]  A[3]  A[4]  A[5]  A[6] A[7] A[8] A[9] 

n = 10 and F_{k} = 13
Let key = 39 and F_{k-1} = 8
If key < A[8] is true, 
Then search A[0:7] = { 10, 34, 39, 45, 53, 58, 66, 75 }

Step 5:

If the given key is greater than the array element at F_{k-1}, then search the right sub-tree to F_{k-1}.


10\hspace{3ex}34\hspace{3ex}39\hspace{3ex}45\hspace{3ex}53\hspace{3ex}58\hspace{3ex}66\hspace{3ex}75\hspace{3ex}83\hspace{3ex}88 
A[0] A[1] A[2]  A[3]  A[4]  A[5]  A[6] A[7] A[8] A[9] 

n = 10 and F_{k} = 13
Let key = 83 and F_{k-1} = 8
If key > A[8] is true, 
Then search A[9:9] = { 88 }

Step 6:

If the key is not found, repeat the step step 1 to step 5 as long as F_{k-1} = 0, that is, Fibonacci number >= n. After each iteration the size of array n is reduced.

Fibonacci Search Example

In this example, we will take a sorted array and find the search key with the array using Fibonacci search technique. Each iteration will show you the state of lower index, higher index and current value of size n, and Fibonacci number used to locate the key.

Consider the following sorted (non-decreasing) array with 10 elements.

Iteration 1

Figure 1- Sorted array with 10 elements
Figure 1- Sorted array with 10 elements
There are 10 elements in the above sorted array S. Therefore, 
low = 0
n = 10
high = n-1 = 9
index = get_fibonacci(n) = 8     //because F_{k} = 13 
loc = -1                         //currect location of the key is outside array
flag = 0                         //check whether key is found or not , flag = 1 indicates it is found
key = 65                         // we are trying to find 65 in the array
is key == S[ index + low] ? 
65 == 81 => NO 
is key > S [ index + low] ?
65 > 81 => NO
is key < S[ index + low ] ?
65 < 81 =>YES

high = low + index - 1          // adjust the higher index and keep the low = 0
high = 0 + 8 - 1 = 7
n = high - low + 1              // adjust the size of the array 
n = 7 - 0 + 1 = 8

Iteration 2

Figure 2- key is less than S[8]. We must search left sub-tree. The array size n is adjusted to 8 elements.
Figure 2- key is less than S[8]. We must search left sub-tree. The array size n is adjusted to 8 elements.
There are 8 elements in the above sorted array S. Therefore, 
low = 0
n = 8
high = 7
index = get_fibonacci(n) =  5    //because previous F_{k} = 8 
loc = -1                         //currect location of the key is outside array
flag = 0                         //check whether key is found or not , flag = 1 indicates it is found
key = 65                         // we are trying to find 65 in the array
is key == S[ index + low] ? 
65 == 54 => NO 
is key > S [ index + low] ?
65 > 54 => YES                  // key is higher than the array element S[5], move to right sub=-tree

low = low + index + 1           // adjust the lower index and keep the high = 7
low = 0 + 5 + 1 = 6
n = high - low + 1              // adjust the size of the array 
n = 7 - 6 + 1 = 2

Iteration 3

Figure 3 - We now have only two element in the array to search the key
Figure 3 – We now have only two element in the array to search the key
There are 2 elements in the above sorted array S. Therefore, 
low = 6
n = 2
high = 7
index = get_fibonacci(n) =  1    //because previous F_{k} = 5
loc = -1                         //currect location of the key is outside array
flag = 0                         //check whether key is found or not , flag = 1 indicates it is found
key = 65                         // we are trying to find 65 in the array
is key == S[ index + low] ? 
65 == 75 => NO 
is key > S [ index + low] ?      // key is higher than the array element S[1], move to right sub=-tree
65 > 75 => NO 
is key < S[ index + low ] ?      // key is higher than the array element S[1], move to left sub=-tree
65 < 81 =>YES                

high = low + index - 1           // adjust the lower index and keep the high = 7
high =  6 + 1 - 1 = 6
n = high - low + 1              // adjust the size of the array 
n = 6 - 6 + 1 = 1

Iteration 4

Figure 4 - Now only one element is remained in the array which is the key
Figure 4 – Now only one element is remained in the array which is the key
Only 1 element remained in the array, still we must go through the iteration.
low = 6
n = 1
high = 6
index = get_fibonacci(n) =  0    // because when n = 0 or n = 1, simply return 0.
loc = -1                         //currect location of the key is outside array
flag = 0                         //check whether key is found or not , flag = 1 indicates it is found
key = 65                         // we are trying to find 65 in the array
is key == S[ index + low] ?      // A[ 6 + 0] = S[6] = 65
65 == 65 => YES
flag = 1
Key is found !

Time Complexity of Fibonacci Search

Here is the Fibonacci search decision tree for n=10.

Figure 5- Fibonacci Search Decision Tree
Figure 5- Fibonacci Search Decision Tree

The Fibonacci search also perform like binary search on a sorted array; therefore, the time complexity is in worst case is O( log\hspace{1ex} n).

We can clearly note a few things from the above decision tree.

If the difference in index of grandparents and parent of a node is F_{k}s=1 then

  • The left sub-tree is of order F_{k-1}s=1.
  • The left sub-tree is of order F_{k-2}s=1.
  • This is true for every sub-tree.
  • The difference between parent and both children is the same.
  • The leftmost path represents a Fibonacci sequence that starts with 0, 1, 2, 3, … .

C++ Implementation Of Fibonacci Search Algorithm

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
int get_fib(int);
int main()
{
  int S[10]= { 5, 23, 34, 42, 48, 54, 65, 75, 81, 95 };
  int n,key, index, low, high, loc, flag;
  n = 10;
  low = 0;
  int location = -1;
  high = n-1;
  flag = 0;  //Read the key
  cout << "Enter Key To Search:";
  cin >> key;
  index = 0;
  while ( flag != 1 && low <= high)
  {
     index = get_fib(n);
     if ( key == S[index + low])
     {
	location = low + index;
	flag = 1;
	break;
     }
     else if( key > S[index + low])
     {
	low = low + index + 1;
     }
     else
     {
	high = low + index -1;
     }
     n = high - low + 1;
  }
     if ( flag == 1)
     {
	cout << "Element Found at Index =" << location << endl;
     }

  getch();
  return 0;
  }

int get_fib(int n)
{
  int fibk = 0;
  int fibk2 = 0;
  int fibk1 = 1;
  if( n == 0 || n == 1)
  {
     return 0;
  }
      while(fibk < n)
      {
	 fibk = fibk1 + fibk2;
	 fibk2 = fibk1;
	 fibk1 = fibk;
      }
      return fibk2;
 }

Input

Enter Key To Search:65

Output

Element Found at Index = 6

In the next post, we shall discuss about searching though Hash Table.

Please support us by disabling your adblocker or whitelist this site from your adblocker. Thanks!

turn of adblocker imag