Fibonacci Search in JavaScript

Introduction

Fibonacci Search is a type of fascinating algorithms that reveals us the sweetness and class of laptop science. Based mostly on the well-known Fibonacci Sequence, the place every quantity is the sum of the 2 previous ones, the Fibonacci Search approach is a comparison-based search algorithm that applies this mathematical idea to search out a component in a sorted array.

Now, you would possibly surprise, how does it work, and much more importantly, and the way can we implement it in JavaScript?! I intention to simply that on this quick article.

Fibonacci Search

The Fibonacci Search makes use of a divide-and-conquer strategy to go looking a component in a sorted array by leveraging the golden properties of the Fibonacci Sequence. By making a set of Fibonacci numbers that act as indices, the search narrows down the attainable areas with the help of these numbers.

Be aware: The Fibonacci Search algorithm is especially environment friendly for big datasets, because it offers a median time complexity of O(log n).

Implementing Fibonacci Search in JavaScript

So, let’s get to writing a operate to carry out a Fibonacci Search. Here is what our code would possibly seem like:

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

    // Create a Fibonacci sequence larger than or equal to the array size
    whereas (fibM < size) {
        fibM2 = fibM1;
        fibM1 = fibM;
        fibM = fibM2 + fibM1;
    }

    let offset = -1;

    whereas (fibM > 1) {
        let i = Math.min(offset + fibM2, size - 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 need to use this operate by calling it with the sorted array and the aspect you wish to discover. It ought to then return the place of the aspect in query.

How does it work?

1. Creating the Fibonacci Sequence: The code initializes the primary two Fibonacci numbers and creates a sequence till it finds a quantity larger than or equal to the size of the array.
2. Dividing the Array: It then divides the array into two elements and checks whether or not the aspect lies within the first or second half.
3. Repeating the Course of: The method is then repeated with the brand new subarray, and the method continues till the aspect is discovered or the subarray measurement turns into zero.

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

Conclusion

Fibonacci Search is as an fascinating utility of mathematical ideas in laptop algorithms. Implementing it in JavaScript provides a contemporary perspective on dealing with sorted knowledge effectively. This algorithm not solely unveils the fascinating properties of mathematical symmetry in laptop science, but additionally offers us a sturdy answer for looking giant datasets.