Fibonacci Search
Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 20 minutes  Coding time: 10 minutes
Fibonacci search is an efficient search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in O(log N) time complexity. This is based on Fibonacci series which is an infinite sequence of numbers denoting a pattern which is captured by the following equation:
F(n+1)=F(n)+F(n1)
where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1 respectively.
The first few Fibonacci numbers are:
0,1,1,2,3,5,8,13....
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) = 1 + 2 = 3 and so continues the series
Other searches like binary search also work for the similar principle on splitting the search space to a smaller space but what makes Fibonacci search different is that it divides the array in unequal parts and operations involved in this search are addition and subtraction only which means light arithmetic operations takes place and hence reducing the work load of the computing machine.
Algorithm
Let the length of given array be n [0...n1] and the element to be searched be x.
Then we use the following steps to find the element with minimum steps:

Find the smallest Fibonacci number greater than or equal to n. Let this number be fb(M) [mβth Fibonacci number]. Let the two Fibonacci numbers preceding it be fb(M1) [(m1)βth Fibonacci number] and fb(M2) [(m2)βth Fibonacci number].

While the array has elements to be checked:
> Compare x with the last element of the range covered by fb(M2)
> If x matches, return index value
> Else if x is less than the element, move the third Fibonacci variable two Fibonacci down, indicating removal of approximately twothird of the unsearched array.
> Else x is greater than the element, move the third Fibonacci variable one Fibonacci down. Reset offset to index. Together this results into removal of approximately front onethird of the unsearched array.
 Since there might be a single element remaining for comparison, check if fbMm1 is '1'. If Yes, compare x with that remaining element. If match, return index value.
From the above algorithm it is clear if we have to search the larger section of the array then the time taken will be more and will result into worst case and it's complexity wil be O(log n). If on the very first search, we get our element then it will be considered as the best case and complexcity will be O(1). When we consider the average case then case left and lies between the best and worst i when we have to search the element on the smaller section of the array and hence we get our average case complexity as O(log n).
Example
Let the given array be :
The element do be found be 100
According to the algorithm we will first sort the array.
 Then check the value in Fibonacci series which is greater or equal to value of n=7
7 <=8
fbM=8 fbM1=5 fbM2=3 offset=1
i=2 //1+3 < 7 min((offset+fBM2),n1)
A[2]=30 < 100
fbM=5 fbM1=3 fbM2=2 offset=2
i=5//2+3<7 min((offset+fBM2),n1)
A[5]=100 = 100
Hence number found in 5th position
Pseudocode
The pseudocode of the Fibonacci search algorithm is:
/* Returns index of x if present, else returns 1 */
int fibonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fbM2 = 0; // (m2)'th Fibonacci number
int fbM1 = 1; // (m1)'th Fibonacci number
int fbM = fbM2 + fbM1; // m'th Fibonacci
// Marks the eliminated range from front
int offset = 1;
/* fbM is going to store the smallest Fibonacci
number greater than or equal to n */
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
/* while there are elements to be inspected. Note that
we compare arr[fbM2] with x. When fbM becomes 1,
fbMm2 becomes 0 */
while (fbM > 1)
{
// Check if fbMm2 is a valid location
int i = min(offset+fbM2, n1);
/* If x is greater than the value at index fbMm2,
cut the subarray array from offset to i */
if (arr[i] < x)
{
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM  fbM1;
offset = i;
}
/* If x is greater than the value at index fbMm2,
cut the subarray after i+1 */
else if (arr[i] > x)
{
fbM = fbM2;
fbM1 = fbM1  fbM2;
fbM2 = fbM  fbM1;
}
/* element found. return index */
else return i;
}
/* comparing the last element with x */
if(fbM1 && arr[offset+1]==x)
return offset+1;
/*element not found. return 1 */
return 1;
Implementations
 C
C++
#include<iostream.h>
#include<conio.h>
/* Find min of given number */
int min(int x, int y)
{
return (x<=y)? x : y;
}
/* Returns index of x if present, else returns 1 */
int fibonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fbM2 = 0; // (m2)'th Fibonacci number
int fbM1 = 1; // (m1)'th Fibonacci number
int fbM = fbM2 + fbM1; // m'th Fibonacci
// Marks the eliminated range from front
int offset = 1;
/* fbM is going to store the smallest Fibonacci
number greater than or equal to n */
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
/* while there are elements to be inspected. Note that
we compare arr[fibM2] with x. When fbM becomes 1,
fbM2 becomes 0 */
while (fbM > 1)
{
// Check if fbM2 is a valid location
int i = min(offset+fbM2, n1);
/* If x is greater than the value at index fbM2,
cut the subarray array from offset to i */
if (arr[i] < x)
{
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM  fbM1;
offset = i;
}
/* If x is greater than the value at index fbMm2,
cut the subarray after i+1 */
else if (arr[i] > x)
{
fbM = fbM2;
fbM1 = fbM1  fbM2;
fbM2 = fbM  fbM1;
}
/* element found. return index */
else return i;
}
/* comparing the last element with x */
if(fbM1 && arr[offset+1]==x)
return offset+1;
/*element not found. return 1 */
return 1;
}
/* main function */
int main(void)
{
clrscr();
int l;
cout<<"\nEnter the number of elements in array which should be less than 10";
cin>>l;
int arr[10];
cout<<"Enter elements in array";
for(int i=0;i<l;i++)
{
cin>>arr[i];
}
int n = sizeof(arr)/sizeof(arr[0]);
int x;
cout<<"\nEnter element to be searched :" ;
cin>>x;
cout<<"Found at index:"<<fib1onaccianSearch(arr, x, n);
getch();
return 0;
}
Complexity
 Worst case time complexity:
Ξ(logn)
 Average case time complexity:
Ξ(log n)
 Best case time complexity:
Ξ(1)
 Space complexity:
Ξ(1)
With each step, the search space is reduced by 1/3 on average, hence, the time complexity is O(log N) where the base of the logarithm is 3.
Applications
Key points about Fibonacci search are:

Fibonacci Search examines closer elements in few steps. So when input array is big that cannot fit in CPU cache or in RAM, it is useful.

On average, fibonacci search requires 4% more comparisons than binary search

Fibonacci search requires only addition and subtraction whereas binary search requires bitshift, division or multiplication operations.

Fibonacci search can reduce the time needed to access an element in a random access memory.

On magnetic tape where seek time depends on the current head position, there are two considerations: longer seek time and more comparisons that leads to prefer Fibonacci search