Fibonacci Search is an interesting and efficient searching algorithm that works on sorted arrays. Unlike Linear Search, which checks each element one by one, or Binary Search, which splits the array in halves, Fibonacci Search uses Fibonacci numbers to divide the array into sections for searching. This unique approach allows it to reduce the number of comparisons, making it particularly efficient for certain types of large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, Fibonacci Search is a great way to learn how mathematical sequences like Fibonacci numbers can be applied to programming problems. It is often used in applications where array access is costly, such as in databases or large file systems, because it reduces the number of comparisons compared to traditional search methods. By understanding this algorithm, learners can strengthen their problem-solving skills and get more comfortable with combining math and programming concepts.
Program 1: Basic Fibonacci Search
This program demonstrates a simple Fibonacci Search on a sorted array.
function fibonacciSearch(arr, target) {
let n = arr.length;
let fibMMm2 = 0; // (m-2)'th Fibonacci
let fibMMm1 = 1; // (m-1)'th Fibonacci
let fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
let offset = -1;
while (fibM > 1) {
let i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 -= fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else return i;
}
if (fibMMm1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let numbers = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
let result = fibonacciSearch(numbers, target);
console.log(result !== -1 ? `Element found at index ${result}` : "Element not found");This program works by using Fibonacci numbers to determine the index to check in the array. Beginners can understand it as “jump ahead by Fibonacci numbers to narrow the search” rather than checking sequentially. It is useful for searching large datasets efficiently.
Program 2: Recursive Fibonacci Search
This example shows Fibonacci Search implemented with a recursive approach for a more mathematical perspective.
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
function fibonacciSearchRecursive(arr, target, offset = -1) {
let n = arr.length;
let fibM = 1;
let fibMm1 = 1;
let fibMm2 = 0;
while (fibM < n) {
fibMm2 = fibMm1;
fibMm1 = fibM;
fibM = fibMm1 + fibMm2;
}
function search(fM, fMm1, fMm2, offset) {
if (fM <= 1) return arr[offset + 1] === target ? offset + 1 : -1;
let i = Math.min(offset + fMm2, n - 1);
if (arr[i] < target)
return search(fMm1, fMm2, fMm1 - fMm2, i);
else if (arr[i] > target)
return search(fMm2, fMm1 - fMm2, fMm2 - (fMm1 - fMm2), offset);
else return i;
}
return search(fibM, fibMm1, fibMm2, offset);
}
let values = [2, 4, 6, 8, 10, 12, 14, 16];
let searchTarget = 12;
let resultRecursive = fibonacciSearchRecursive(values, searchTarget);
console.log(resultRecursive !== -1 ? `Element found at index ${resultRecursive}` : "Element not found");This recursive approach demonstrates how the Fibonacci sequence can guide search positions. Beginners can think of it as “repeatedly narrowing the array using Fibonacci steps.” It is useful for understanding how recursion and sequences can work together in algorithm design.
Program 3: Fibonacci Search for first occurrence
This program shows how to find the first occurrence of a target in a sorted array with duplicates using Fibonacci Search.
function fibonacciSearchFirst(arr, target) {
let n = arr.length;
let fibMMm2 = 0;
let fibMMm1 = 1;
let fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
let offset = -1;
let result = -1;
while (fibM > 1) {
let i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else {
if (arr[i] === target) result = i;
fibM = fibMMm2;
fibMMm1 -= fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
}
if (fibMMm1 && arr[offset + 1] === target) result = offset + 1;
return result;
}
let numbersDup = [1, 2, 2, 2, 3, 4, 5];
let targetDup = 2;
console.log("First occurrence index:", fibonacciSearchFirst(numbersDup, targetDup));This program works by continuing the search even after finding a match to ensure the first occurrence is returned. Beginners can understand it as “keep moving left if possible to find the first match.” It is useful for sorted arrays containing duplicates.
Program 4: Fibonacci Search for last occurrence
This example demonstrates finding the last occurrence of a target using Fibonacci Search.
function fibonacciSearchLast(arr, target) {
let n = arr.length;
let fibMMm2 = 0;
let fibMMm1 = 1;
let fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
let offset = -1;
let result = -1;
while (fibM > 1) {
let i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else {
if (arr[i] === target) result = i;
fibM = fibMMm2;
fibMMm1 -= fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
}
if (fibMMm1 && arr[offset + 1] === target) result = offset + 1;
return result;
}
let data = [5, 7, 7, 7, 8, 9, 10];
let targetValue = 7;
console.log("Last occurrence index:", fibonacciSearchLast(data, targetValue));This program searches right to locate the last match. Beginners can understand it as “continue to update the last found index while searching right.” It is helpful for counting duplicates or determining ranges.
Program 5: Fibonacci Search as a reusable function
This program wraps Fibonacci Search into a reusable function for multiple datasets.
function fibonacciSearchUtility(arr, target) {
let n = arr.length;
let fibMMm2 = 0;
let fibMMm1 = 1;
let fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
let offset = -1;
while (fibM > 1) {
let i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 -= fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else return i;
}
if (fibMMm1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let numbersSet = [3, 6, 9, 12, 15, 18, 21];
let findNum = 12;
let resultUtility = fibonacciSearchUtility(numbersSet, findNum);
console.log(resultUtility !== -1 ? `Element found at index ${resultUtility}` : "Element not found");This reusable function allows beginners to search any sorted array efficiently using Fibonacci Search, demonstrating modularity and clarity while leveraging algorithmic efficiency.
Frequently Asked Questions (FAQ)
This section addresses common beginner questions about Fibonacci Search in JavaScript.
Q1. What is Fibonacci Search?
Fibonacci Search is a search algorithm that uses Fibonacci numbers to determine which indices to check in a sorted array, making searches efficient.
Q2. Can Fibonacci Search be used on unsorted arrays?
No, the array must be sorted for Fibonacci Search to work correctly.
Q3. How is Fibonacci Search different from Binary Search?
Binary Search splits the array in halves, while Fibonacci Search uses Fibonacci numbers to split the array in a slightly uneven but optimized way.
Q4. What is the time complexity of Fibonacci Search?
The time complexity is O(log n), similar to Binary Search, but it may reduce the number of comparisons in some scenarios.
Q5. Why should beginners learn Fibonacci Search?
It introduces mathematical thinking in programming and helps learners understand advanced search techniques beyond basic linear and binary search.
Conclusion
Fibonacci Search is an efficient and interesting algorithm for searching in sorted arrays, combining mathematical sequences with programming logic.
By practicing iterative, recursive, first/last occurrence, and reusable function implementations, beginners can strengthen their understanding of efficient search strategies in JavaScript. Learning Fibonacci Search also helps improve algorithmic thinking, modular coding practices, and confidence in handling large datasets effectively.
