Fibonacci Search is an interesting and efficient searching algorithm designed for sorted arrays. Unlike Binary Search, which divides the search space into halves, Fibonacci Search uses Fibonacci numbers to split the array into sections. This approach can be particularly effective for large arrays and provides a unique way to locate elements quickly. For beginners learning TypeScript, implementing Fibonacci Search is a great way to understand how mathematical sequences can be applied to programming problems.
with hands-on learning.
get the skills and confidence to land your next move.
This algorithm is useful in applications like searching in large databases, looking up values in sorted records, or optimizing search operations where efficiency matters. By understanding Fibonacci Search, beginners not only learn a practical searching technique but also gain insight into how combining mathematical concepts with programming can solve real-world problems effectively.
Program 1: Iterative Fibonacci Search
This program demonstrates the standard iterative approach to Fibonacci Search, using Fibonacci numbers to calculate the index to check.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let data: number[] = [1, 3, 5, 7, 9, 11, 13, 15];
let targetValue: number = 9;
console.log("Element found at index:", fibonacciSearch(data, targetValue));This program calculates Fibonacci numbers to determine which index to check, reducing the number of comparisons. Beginners can see how math helps guide the search efficiently.
Program 2: Recursive Fibonacci Search
Fibonacci Search can also be implemented recursively, using the Fibonacci sequence to guide index selection at each recursive call.
function fibonacciSearchRecursive(arr: number[], target: number, fibM: number, fibMm1: number, fibMm2: number, offset: number = -1): number {
if (fibM === 0) return -1;
let i = Math.min(offset + fibMm2, arr.length - 1);
if (arr[i] < target) {
return fibonacciSearchRecursive(arr, target, fibMm1, fibMm2, fibMm1 - fibMm2, i);
} else if (arr[i] > target) {
return fibonacciSearchRecursive(arr, target, fibMm2, fibMm1 - fibMm2, fibMm2 - (fibMm1 - fibMm2), offset);
} else {
return i;
}
}
let numbers: number[] = [2, 4, 6, 8, 10, 12, 14];
let fib2 = 0, fib1 = 1, fib = fib1 + fib2;
while (fib < numbers.length) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; }
console.log("Element found at index:", fibonacciSearchRecursive(numbers, 12, fib, fib1, fib2));This recursive implementation helps beginners understand how Fibonacci numbers can guide a divide-and-conquer search strategy.
Program 3: Fibonacci Search for Negative Numbers
Fibonacci Search can handle negative numbers in a sorted array without any changes.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let negatives: number[] = [-50, -40, -30, -20, -10, 0, 10];
let targetNegative: number = -20;
console.log("Element found at index:", fibonacciSearch(negatives, targetNegative));Beginners can see that comparisons work the same for negative numbers, making the algorithm flexible.
Program 4: Fibonacci Search for Floating Point Numbers
Fibonacci Search can also locate decimal values in sorted arrays.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let decimals: number[] = [0.5, 1.0, 1.5, 2.0, 2.5, 3.0];
let targetDecimal: number = 2.0;
console.log("Element found at index:", fibonacciSearch(decimals, targetDecimal));This shows the algorithm’s versatility for real-world data where numbers are not always integers.
Program 5: Fibonacci Search for Large Arrays
Fibonacci Search performs efficiently even in large arrays due to its guided search mechanism.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2);
let targetLarge: number = 800;
console.log("Element found at index:", fibonacciSearch(largeArray, targetLarge));Beginners can observe how the algorithm quickly narrows down the search space without checking each element individually.
Program 6: Fibonacci Search for Duplicate Values
This program demonstrates searching for targets in arrays with duplicate values.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let duplicates: number[] = [5, 10, 10, 15, 20, 20, 25];
let targetDuplicate: number = 20;
console.log("Element found at index:", fibonacciSearch(duplicates, targetDuplicate));The algorithm efficiently finds an occurrence of the target without scanning sequentially, showing its usefulness in real datasets.
Program 7: Fibonacci Search in Uniform Data
Fibonacci Search works well for uniformly distributed arrays too.
function fibonacciSearch(arr: number[], target: number): number {
let fib2 = 0; // (m-2)'th Fibonacci number
let fib1 = 1; // (m-1)'th Fibonacci number
let fib = fib1 + fib2; // m'th Fibonacci number
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
let i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}
let uniformData: number[] = [10, 20, 30, 40, 50, 60, 70];
let targetUniform: number = 40;
console.log("Element found at index:", fibonacciSearch(uniformData, targetUniform));This highlights that the method is applicable for arrays with consistent spacing or varying differences as long as they are sorted.
Frequently Asked Questions (FAQ)
Beginners often ask questions about Fibonacci Search:
Q1. Can Fibonacci Search work on unsorted arrays?
No, the array must be sorted for correct results.
Q2. How is Fibonacci Search different from Binary Search?
It uses Fibonacci numbers to calculate indices instead of midpoints, which can improve performance for certain datasets.
Q3. Can Fibonacci Search handle negative numbers and decimals?
Yes, it works with all numeric types in sorted arrays.
Q4. Is Fibonacci Search efficient for large arrays?
Yes, it narrows down the search space quickly using the Fibonacci sequence.
Q5. Does Fibonacci Search return the first occurrence of a duplicate?
No, it may return any occurrence; additional logic is required for first or last occurrence.
Conclusion
Fibonacci Search is an efficient algorithm for finding elements in sorted arrays. In this article, we explored TypeScript programs implementing Fibonacci Search using iteration, recursion, negative numbers, decimals, duplicates, and large arrays. Each example showed how Fibonacci numbers can guide the search process efficiently, reducing comparisons and optimizing performance.
Beginners can practice these examples to strengthen their understanding of searching algorithms, recursion, and how mathematical concepts like the Fibonacci sequence can be applied in programming. Mastering Fibonacci Search opens the door to more advanced search techniques and efficient problem-solving in real-world applications.
