459 words

2 minutes

# 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

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

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

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

- Compare the target value
**Check the last element:**- After the loop, check if the last element (when
`fibM`

is 1) matches the target value.

- After the loop, check if the last element (when
**Return result:**- Return the index if the element is found; otherwise, return
`-1`

.

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

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