Fibonacci Search

  2. Tutorial
  3. Algorithm
  4. Fibonacci Search
Harshit Jindal Oct 12, 2023
Algorithm Search Algorithm
  1. Fibonacci Search Algorithm
  2. Fibonacci Search Example
  3. Fibonacci Search Algorithm Implementation
  4. Fibonacci Search Algorithm Complexity
Fibonacci Search

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 mth 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.
  • 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.
  • 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) {
    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.

Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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

Related Article - Search Algorithm