# Fibonacci Search

Fibonacci search is an efficient interval searching algorithm. It is similar to binary search in the sense that it is also based on the divide and conquer strategy and it also needs the array to be sorted. Moreover, the time complexity for both algorithms is logarithmic. It is called Fibonacci search because it utilizes the Fibonacci series (The current number is the sum of two predecessors `F[i] = F[i-1] + F[i-2]`, `F`=`0` &`F`=`1` are the first two numbers in series.) and divides the array into two parts with size given by Fibonacci numbers. It is a computation-friendly method that uses only addition and subtraction operations compared to division, multiplication, and bit-shifts required by binary search.

## Fibonacci Search Algorithm

Let us assume that we have an unsorted array `A[]` containing `n` elements, and we want to find an element - `X`.

• ##### While `fib(m-2)` is greater than `0` do the following:
• Compare `X` with the last element covered by `fib(m-2)`. It is given by `A[min(offset + fib(m-2), n - 1)]`.
• If `X` equals this element, then return the index.
• Else if `X` is smaller than this element, we discard the half after this element and move the Fibonacci sequence two steps backward. Also, update the offset to change the starting index of search space. These steps discard the rear two-third of the array search space.
• Else if `X` is greater than this element, we discard the half before this element and move the Fibonacci sequence one step backward. This step discards the front one-third of the array search space.

## Fibonacci Search Example

Suppose we have the array: `(1, 2, 3, 4, 5, 6, 7)`. We have to look for the element `X` = 6.

The array has 7 elements. So, `n` = 7. The smallest Fibonacci number greater than `n` is 8.

• ##### First Iteration
• We compute the index of the element as `min(-1 + 3, 6)` giving us the element as `A = 3`.
• `3` < `6` i.e. `A` < `X` hence we discard `A[0....2]` and set `offset` as `2`.
• We also update the Fibonacci sequence to move `fib(m-2)` to `2`, `fib(m-1)` to `3` and `fib(m)` to `5`.
• ##### Second Iteration
• We compute the index of the element as `min(2 + 2, 6)` giving us the element as `A = 5`.
• `5` < `6` i.e. `A` < `X` hence we discard `A[2 .... 4]` and set `offset` as `4`.
• We also update the Fibonacci sequence to move `fib(m-2)` to `1`, `fib(m-1)` to `2` and `fib(m)` to `3`.
• ##### Third Iteration
• We compute the index of the element as `min(4 + 1, 6)` giving us the element as `A = 6`.
• `6` == `6` i.e. `A` == `X` , we return the index `5`.

## Fibonacci Search Algorithm Implementation

``````#include <bits/stdc++.h>
using namespace std;

int fibonacciSearch(int A[], int x, int n)
{
int fbM2 = 0;
int fbM1 = 1;
int fbM = fbM2 + fbM1;
int offset = -1;
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM  = fbM2 + fbM1;
}
while (fbM > 1)
{
int i = min(offset + fbM2, n - 1);
if (A[i] < x)
{
fbM  = fbM1;
fbM1 = fbM2;
fbM2 = fbM - fbM1;
offset = i;
}
else if (A[i] > x)
{
fbM  = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}
else return i;
}
if (fbM1 && A[offset + 1] == x)
return offset + 1;

return -1;
}

int main()
{
int n = 9;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 8;
int result = fibonacciSearch(arr, x, n);
if (result == -1) {
}
else cout << "Element found at index " << result;
return 0;
}
``````

## Fibonacci Search Algorithm Complexity

### Time Complexity

• Average Case

We reduce the search space by one-third / two-third in every iteration, and hence the algorithm has a logarithmic complexity. The time complexity of the Fibonacci Search Algorithm is `O(logn)`.

• Best Case

The best-case time complexity is `O(1)`. It occurs when the element to be searched is the first element we compare.

• Worst-Case

The worst-case occurs when the target element `X` is always present in the larger subarray. The worst-case time complexity is `O(logn)`. It is the same as average-case time complexity.

### Space Complexity

The space complexity of this algorithm is `O(1)` because no extra space other than temporary variables is required.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

## Related Article - Search Algorithm

• Interpolation Search