Fibonacci Search in JavaScript

Introduction

Fibonacci Search is a kind of attention-grabbing algorithms that reveals us the wonder and magnificence of pc science. Primarily based 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 marvel, 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 look 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 potential places with the help of these numbers.

Observe: The Fibonacci Search algorithm is especially environment friendly for giant datasets, because it supplies a mean 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 appear to be:

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

    // Create a Fibonacci sequence higher 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 should utilize this operate by calling it with the sorted array and the ingredient you need to discover. It ought to then return the place of the ingredient 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 higher 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 ingredient 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 ingredient is discovered or the subarray dimension 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 attention-grabbing software of mathematical ideas in pc algorithms. Implementing it in JavaScript affords a contemporary perspective on dealing with sorted information effectively. This algorithm not solely unveils the attention-grabbing properties of mathematical symmetry in pc science, but in addition provides us a strong resolution for looking out giant datasets.