# Fibonacci Search

Harshit Jindal Oct 12, 2023

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

• ##### 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[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`.
• ##### 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`.
• ##### 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`.

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

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.