Fibonacci Search in JavaScript

Fibonacci Search is an efficient algorithm for searching a sorted array using the Fibonacci sequence. It’s particularly useful when the array is large and you want to minimize the number of comparisons.

Here’s a basic implementation of Fibonacci Search in JavaScript:

// Function to find the minimum of two numbers
function min(a, b) {
    return a < b ? a : b;
}

// Function to perform Fibonacci Search
function fibonacciSearch(arr, x) {
    let n = arr.length;

    // Initialize Fibonacci numbers
    let fibM = 0; // Fibonacci M
    let fibM1 = 1; // Fibonacci M-1
    let fibM2 = 0; // Fibonacci M-2

    // Find the smallest Fibonacci number greater than or equal to n
    while (fibM < n) {
        fibM = fibM1 + fibM2;
        fibM2 = fibM1;
        fibM1 = fibM;
    }

    // Marks the eliminated range from front
    let offset = -1;

    // While there are elements to be inspected
    while (fibM > 1) {
        // Check if fibM2 is a valid location
        let i = min(offset + fibM2, n - 1);

        // If x is greater than the value at index i, cut the subarray from offset to i
        if (arr[i] < x) {
            fibM = fibM1;
            fibM1 = fibM2;
            fibM2 = fibM - fibM1;
            offset = i;
        }
        // If x is smaller than the value at index i, cut the subarray after i+1
        else if (arr[i] > x) {
            fibM = fibM2;
            fibM1 = fibM1 - fibM2;
            fibM2 = fibM - fibM1;
        }
        // Element found, return index
        else {
            return i;
        }
    }

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

    // Element not found
    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);

if (index !== -1) {
    console.log(`Element found at index ${index}`);
} else {
    console.log("Element not found in the array");
}

Explanation#

1. Initialization:

   • fibM, fibM1, and fibM2 are used to keep track of the current Fibonacci numbers. We start by setting fibM2 to 0 and fibM1 to 1, and then calculate fibM as their sum.

2. Find the smallest Fibonacci number greater than or equal to the array size:

   • This ensures that the Fibonacci number we are using is sufficient to cover the entire array.

3. Perform the search:

   • Compare the target value x with the element at the calculated index.
   • Adjust the Fibonacci numbers and the offset based on whether the target value is smaller or larger than the current element.

4. Check the last element:

   • After the loop, check if the last element (when fibM is 1) matches the target value.

5. Return result:

   • Return the index if the element is found; otherwise, return -1.

Feel free to adjust the implementation based on your specific needs!