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[i1] + F[i2]
, 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 computationfriendly method that uses only addition and subtraction operations compared to division, multiplication, and bitshifts 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 numberfib(m)
and its predecessorfib(m1)
andfib(m2)
. 
Initialize offset as
1
. 
While
fib(m2)
is greater than0
do the following: Compare
X
with the last element covered byfib(m2)
. It is given byA[min(offset + fib(m2), 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 twothird 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 onethird of the array search space.
 Compare

If
fib(m1)
equals1
we have one element left unchecked, compare it withX
.IfX
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(m1)
=5
andfib(m2)
=3
. 
First Iteration
 We compute the index of the element as
min(1 + 3, 6)
giving us the element asA[2] = 3
. 3
<6
i.e.A[2]
<X
hence we discardA[0....2]
and setoffset
as2
. We also update the Fibonacci sequence to move
fib(m2)
to2
,fib(m1)
to3
andfib(m)
to5
.
 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 asA[4] = 5
. 5
<6
i.e.A[4]
<X
hence we discardA[2 .... 4]
and setoffset
as4
. We also update the Fibonacci sequence to move
fib(m2)
to1
,fib(m1)
to2
andfib(m)
to3
.
 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 asA[5] = 6
. 6
==6
i.e.A[5]
==X
, we return the index5
.
 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 onethird / twothird 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 bestcase time complexity is O(1)
. It occurs when the element to be searched is the first element we compare.
 WorstCase
The worstcase occurs when the target element X
is always present in the larger subarray. The worstcase time complexity is O(logn)
. It is the same as averagecase 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.
LinkedIn