68 total views

The **Fibonacci search **alg*orithm* 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).

Contents

#### The Fibonacci Sequence

Simply said the Fibonacci sequence is a set of numbers where any term 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.

\begin{aligned} &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 \end{aligned}

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 and fibonacci number is .

We must find a such that

if then we must find a .

The Fibonacci sequence is

\begin{aligned}0, 1, 1, 2, 3, 5, 8, 13, ...\end{aligned}

Therefore, because .

**Step 2:**

The next step is to compare the key with the element at Fibonacci number .

We know that because . We must find the .

Once again we look at the Fibonacci sequence is

\begin{aligned} 0, 1, 1, 2, 3, 5, 8, 13, ...\end{aligned}

Since,

**Step 3:**

If the key and array element at are equal then the key is at .

For example, we are searching within an array of 10 elements.

\begin{aligned}&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]\hspace{1ex} A[1] \hspace{1ex} A[2] \hspace{1ex} A[3] \hspace{1ex} A[4] \hspace{1ex} A[5] \hspace{1ex}A [6] \hspace{1ex} A[7] \hspace{1ex} A[8] \hspace{1ex} A[9]\end{aligned}

and

Let and

Therefore, key == A[8] is true.

Then the key is found at which is position.

**Step 4:**

If the *key is less than array element* at , then search the **left sub-tree** to .

For example, we are searching within an array of 10 elements.

\begin{aligned} &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] \hspace{1ex} A[1]\hspace{1ex} A[2] \hspace{1ex} A[3] \hspace{1ex} A[4]\hspace{1ex} A[5] \hspace{1ex} A[6] \hspace{1ex} A[7]\hspace{1ex} A[8] \hspace{1ex} A[9]\end{aligned}

and

Let and

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 , then search the **right sub-tree** to .

\begin{aligned} &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]\hspace{1ex} A[1] \hspace{1ex} A[2] \hspace{1ex} A[3] \hspace{1ex} A[4] \hspace{1ex} A[5] \hspace{1ex} A[6] \hspace{1ex} A[7] \hspace{1ex} A[8] \hspace{1ex} A[9]\end{aligned}

and

Let and

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 , that is, **Fibonacci number >= n**. After each iteration the size of array 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**

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**

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**

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**

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 .

The Fibonacci search also perform like binary search on a sorted array; therefore, the time complexity is in worst case is .

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 then

- The left sub-tree is of order .
- The left sub-tree is of order .
- 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.

Bestseller

**Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition**

Best book for students with little programming experience. The algorithms are designed and explained in easy to understand manner. The book includes many exercises and problems. The text is intended primarily for students studying algorithms or data structures. As it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals.