# Fibonacci Search

- Fibonacci Search Algorithm
- Fibonacci Search Example
- Fibonacci Search Algorithm Implementation
- Fibonacci Search Algorithm Complexity

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]`

=`0`

&`F[1]`

=`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`

.

##### Find the smallest Fibonacci number just greater than or equal to the size of array

`n`

. Let this number be m^{th}Fibonacci number`fib(m)`

and its predecessor`fib(m-1)`

and`fib(m-2)`

.##### Initialize offset as

`-1`

.##### 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.

- Compare
##### If

`fib(m-1)`

equals`1`

we have one element left unchecked, compare it with`X`

.If`X`

equals this element then return the index.##### If none of the elements matched, then return

`-1`

.

## 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.

##### We get

`fib(m)`

=`8`

,`fib(m-1)`

=`5`

and`fib(m-2)`

=`3`

.##### First Iteration

- We compute the index of the element as
`min(-1 + 3, 6)`

giving us the element as`A[2] = 3`

. `3`

<`6`

i.e.`A[2]`

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

.

- We compute the index of the element as
##### Second Iteration

- We compute the index of the element as
`min(2 + 2, 6)`

giving us the element as`A[4] = 5`

. `5`

<`6`

i.e.`A[4]`

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

.

- We compute the index of the element as
##### Third Iteration

- We compute the index of the element as
`min(4 + 1, 6)`

giving us the element as`A[5] = 6`

. `6`

==`6`

i.e.`A[5]`

==`X`

, we return the index`5`

.

- We compute the index of the element as

## 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) {
cout << "Element not found !!";
}
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.