Fibonacci

the Fibonacci Search Algorithm uses Fibonacci numbers to search for an element in a sorted input array.

But first, let us revise our knowledge on Fibonacci numbers −

Fibonacci Series is a series of numbers that have two primitive numbers 0 and 1.

The successive numbers are the sum of preceding two numbers in the series.

This is an infinite constant series, therefore, the numbers in it are fixed.

The first few numbers in this Fibonacci series include −

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

The main idea behind the Fibonacci series is also to eliminate the least possible places where the element could be found.

In a way, it acts like a divide & conquer algorithm (logic being the closest to binary search algorithm).

This algorithm, like jump search and exponential search, also skips through the indices of the input array in order to perform searching.

Fibonacci Search Algorithm

The Fibonacci Search Algorithm makes use of the Fibonacci Series to diminish the range of an array on which the searching is set to be performed.

With every iteration, the search range decreases making it easier to locate the element in the array. The detailed procedure of the searching is seen below −

Step 1 − As the first step, find the immediate Fibonacci number that is greater than or equal to the size of the input array. Then, also hold the two preceding numbers of the selected Fibonacci number, that is, we hold Fm, Fm-1, Fm-2 numbers from the Fibonacci Series.

Step 2 − Initialize the offset value as -1, as we are considering the entire array as the searching range in the beginning.

Step 3 − Until Fm-2 is greater than 0, we perform the following steps −

• Compare the key element to be found with the element at index [min(offset+Fm-2,n-1)]. If a match is found, return the index.

• If the key element is found to be lesser value than this element, we reduce the range of the input from 0 to the index of this element. The Fibonacci numbers are also updated with Fm = Fm-2.

• But if the key element is greater than the element at this index, we remove the elements before this element from the search range. The Fibonacci numbers are updated as Fm = Fm-1. The offset value is set to the index of this element.

Step 4 − As there are two 1s in the Fibonacci series, there arises a case where your two preceding numbers will become 1. So if Fm-1 becomes 1, there is only one element left in the array to be searched. We compare the key element with that element and return the 1st index. Otherwise, the algorithm returns an unsuccessful search.

pseudocode:

function fibonacciSearch(array, key):
    n = length(array)
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    
    while fibM < n:
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    
    offset = -1
    
    while fibM > 1:
        i = min(offset + fibM_minus_2, n - 1)
        
        if array[i] < key:
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            offset = i
        
        else if array[i] > key:
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        
        else:
            return i
    
    if fibM_minus_1 == 1 and array[offset + 1] == key:
        return offset + 1
    
    return -1

Analysis

The Fibonacci Search algorithm takes logarithmic time complexity to search for an element.

Since it is based on a divide on a conquer approach and is similar to idea of binary search, the time taken by this algorithm to be executed under the worst case consequences is O(log n).

function fibonacciSearch(arr, x) {
    let fibMMm2 = 0; // (m-2)'th Fibonacci number
    let fibMMm1 = 1; // (m-1)'th Fibonacci number
    let fibM = fibMMm1 + fibMMm2; // m'th Fibonacci number

    // fibM is going to store the smallest Fibonacci
    // Number greater than or equal to arr.length
    while (fibM < arr.length) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm1 + fibMMm2;
    }

    let offset = -1;

    while (fibM > 1) {
        // Check if fibMMm2 is a valid location
        const i = Math.min(offset + fibMMm2, arr.length - 1);

        // If x is greater than the value at index fibMMm2, cut the subarray array from offset to i
        if (arr[i] < x) {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        }

        // If x is less than the value at index fibMMm2, cut the subarray after i+1
        else if (arr[i] > x) {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        }

        // Element found
        else {
            return i;
        }
    }

    // Compare the last element with x
    if (fibMMm1 && arr[offset + 1] === x) {
        return offset + 1;
    }

    // If the element is not found, return -1
    return -1;
}

// Example usage:
const arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100];
const x = 85;
const index = fibonacciSearch(arr, x);
console.log("Element found at index:", index);