Fibonacci Search in JavaScript

Introduction

Fibonacci Search is one of those interesting algorithms that shows us the beauty and elegance of computer science. Based on the famous Fibonacci Sequence, where each number is the sum of the two preceding ones, the Fibonacci Search technique is a comparison-based search algorithm that applies this mathematical concept to find an element in a sorted array.

Now, you might wonder, how does it work, and even more importantly, and how can we implement it in JavaScript?! I aim to just that in this short article.

Fibonacci Search

The Fibonacci Search uses a divide-and-conquer approach to search an element in a sorted array by leveraging the golden properties of the Fibonacci Sequence. By creating a set of Fibonacci numbers that act as indices, the search narrows down the possible locations with the aid of these numbers.

Note: The Fibonacci Search algorithm is particularly efficient for large datasets, as it provides an average time complexity of O(log n).

Implementing Fibonacci Search in JavaScript

So, let's get to writing a function to perform a Fibonacci Search. Here's what our code might look like:

function fibonacciSearch(arr, x) {
    let fibM2 = 0;
    let fibM1 = 1;
    let fibM = fibM2 + fibM1;
    const length = arr.length;

    // Create a Fibonacci sequence greater than or equal to the array length
    while (fibM < length) {
        fibM2 = fibM1;
        fibM1 = fibM;
        fibM = fibM2 + fibM1;
    }

    let offset = -1;

    while (fibM > 1) {
        let i = Math.min(offset + fibM2, length - 1);

        if (arr[i] < x) {
            fibM = fibM1;
            fibM1 = fibM2;
            fibM2 = fibM - fibM1;
            offset = i;
        } else if (arr[i] > x) {
            fibM = fibM2;
            fibM1 = fibM1 - fibM2;
            fibM2 = fibM - fibM1;
        } else {
            return i;
        }
    }

    if (fibM1 && arr[offset + 1] == x) {
        return offset + 1;
    }

    return -1;
}

You can use this function by calling it with the sorted array and the element you want to find. It should then return the position of the element in question.

How does it work?

1. Creating the Fibonacci Sequence: The code initializes the first two Fibonacci numbers and creates a sequence until it finds a number greater than or equal to the length of the array.
2. Dividing the Array: It then divides the array into two parts and checks whether the element lies in the first or second part.
3. Repeating the Process: The process is then repeated with the new subarray, and the process continues until the element is found or the subarray size becomes zero.

The Fibonacci Search divides the array based on Fibonacci numbers, which makes the division close to the golden ratio.

Conclusion

Fibonacci Search is as an interesting application of mathematical principles in computer algorithms. Implementing it in JavaScript offers a fresh perspective on handling sorted data efficiently. This algorithm not only unveils the interesting properties of mathematical symmetry in computer science, but also gives us a robust solution for searching large datasets.