JIYIK CN >

Fibonacci search is an efficient interval search algorithm. It is similar to binary search in that it is also based on a divide-and-conquer strategy and also requires the array to be sorted. In addition, the time complexity of both algorithms is logarithmic. It is called Fibonacci search because it uses the Fibonacci sequence (the current number is the sum of the two previous numbers F[i]=F[i-1]+F[i-2], F[0]= 0& F[1]= 1are the first two numbers in the sequence) to divide the array into two parts of size given by the Fibonacci numbers. Compared with the division, multiplication, and shift required for binary search, it only uses addition and subtraction operations, which is a convenient method for calculation.

Fibonacci search algorithm

Suppose we have an unsorted array A[]containing nelements and we want to find an element - X.

• Find the smallest Fibonacci number that is just greater than or equal to the size of the array n. Let this number be the mth Fibonacci number fib(m) and its predecessors fib(m-1) and fib(m-2).
• Initialize the offset to -1.
• When fib(m-2) is greater than 0, perform the following operations.
  • Compare X to the last element covered by fib(m-2). This is given by A[min(offset + fib(m-2), n - 1)].
  • If X is equal to this element, then the index is returned.
  • Otherwise, if X is less than this element, we discard the last half of this element and move the Fibonacci sequence back two steps. At the same time, we update the offset and change the starting index of the search space. These steps will discard the last half of the array search space.
  • Otherwise, if X is greater than the element, we discard the first half of the element and move the Fibonacci sequence backwards by one step. This step discards the first third of the array search space.
• If fib(m-1) equals 1, we have an element that was not selected, compare it with X. If X is equal to this element, return the index.
• If no element matches, then -1 is returned.

Fibonacci Search Example

Suppose we have array - (1, 2, 3, 4, 5, 6, 7). We have to find element X= 6.

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

• We get fib(m)=8, fib(m-1)=5, fib(m-2)=3.
• First Iteration
  • We calculate the index of the element as min(-1 + 3 , 6 ), and the element we get is A[2] = 3.
  • 3 <6, that is, A[2] < X, so we discard A[0.... 2] and set offset to 2.
  • We also update the Fibonacci sequence, moving fib(m-2) to 2, fib(m-1) to 3, and fib(m) to 5.
• Second Iteration
  • We calculate the index of the element as min(2 + 2, 6) and get the element A[4] = 5.
  • 5<6, that is, A[4]<X, so we discard A[2 .... 4] and set offset to 4.
  • We also update the Fibonacci sequence by moving fib(m-2) to 1, fib(m-1) to 2, and fib(m) to 3.
• Third iteration
  • We calculate the exponent of the element as min(4+1,6), and get the element A[5]=6.
  • 6=6, that is, A[5]=X, and we return index 5.

Implementation of the Fibonacci search algorithm

#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;
}

Complexity of the Fibonacci search algorithm

Time Complexity

• Average situation

We reduce the search space by one third/two thirds in each iteration, so the algorithm has logarithmic complexity. The time complexity of the Fibonacci search algorithm is O(logn).

• Best Case

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

• Worst case scenario

XThe worst case occurs when the target element always exists in the larger subarray. The time complexity of the worst case is O(logn). It is the same as the time complexity of the average case.

Space complexity

The space complexity of this algorithm is O(1)since no additional space is required except for the temporary variables.