W3jar
459 words
2 minutes

# Fibonacci Search in JavaScript

2024-08-04

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;
}

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 {
}


### 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.