Searching efficiently in sorted arrays is one of the first challenges every programmer encounters. While binary search is widely known, Fibonacci search is another interesting algorithm that leverages Fibonacci numbers to determine the positions to check. This technique reduces the range of comparison progressively, making it efficient for large, sorted datasets. Beginners often find Fibonacci search fascinating because it combines mathematical sequences with practical searching algorithms, giving a new perspective on problem-solving in programming.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci search is especially useful in situations where division operations are costly because it only uses addition and subtraction to calculate indices. It is also ideal for systems where data is stored in a sequential-access medium, like tape drives, because it naturally minimizes jumps across memory. Understanding Fibonacci search helps beginners appreciate the relationship between mathematics and algorithms in computer science.
Program 1: Iterative Fibonacci Search
This program demonstrates a simple iterative approach to Fibonacci search using a predefined sorted array.
#include <iostream>
using namespace std;
// Function to find the smallest Fibonacci number greater than or equal to n
int fibM(int n) {
int fibMMm2 = 0; // (m-2)'th Fibonacci
int fibMMm1 = 1; // (m-1)'th Fibonacci
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
return fibM;
}
int fibonacciSearch(int arr[], int n, int key) {
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, n - 1);
if (arr[i] < key) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > key) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else
return i;
}
if (fibMMm1 && arr[offset + 1] == key)
return offset + 1;
return -1;
}
int main() {
int arr[] {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 85;
int result = fibonacciSearch(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}In this program, the Fibonacci numbers determine the positions to check. We narrow down the search range step by step, similar to binary search, but the mid-points are based on Fibonacci numbers. This helps beginners understand how mathematical sequences can guide search strategies.
Program 2: Fibonacci Search with User Input
This version allows the user to enter the element they want to search, making it interactive and practical.
#include <iostream>
using namespace std;
int fibonacciSearchInteractive(int arr[], int n, int key) {
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, n - 1);
if (arr[i] < key) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > key) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else
return i;
}
if (fibMMm1 && arr[offset + 1] == key)
return offset + 1;
return -1;
}
int main() {
int arr[] {5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Enter the element to search: ";
cin >> key;
int result = fibonacciSearchInteractive(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}By letting users enter the search key, beginners can test different scenarios and understand how Fibonacci search adapts to various elements. It reinforces the concept of range reduction using Fibonacci numbers.
Program 3: Recursive Fibonacci Search
This program demonstrates a recursive approach, which provides a more modular structure for beginners to understand.
#include <iostream>
using namespace std;
int fibonacciSearchRecursive(int arr[], int n, int key, int fibM, int fibMMm1, int fibMMm2, int offset) {
if (fibM <= 1)
return (fibMMm1 && arr[offset + 1] == key) ? offset + 1 : -1;
int i = min(offset + fibMMm2, n - 1);
if (arr[i] < key)
return fibonacciSearchRecursive(arr, n, key, fibMMm1, fibMMm2, fibMMm1 - fibMMm2, i);
else if (arr[i] > key)
return fibonacciSearchRecursive(arr, n, key, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2), offset);
else
return i;
}
int main() {
int arr[] {2, 3, 4, 10, 14, 19, 27, 33, 41};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 19;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int result = fibonacciSearchRecursive(arr, n, key, fibM, fibMMm1, fibMMm2, -1);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}The recursive version demonstrates how a divide-and-conquer strategy can be applied using Fibonacci numbers. Beginners can see how recursion naturally reduces the search space while maintaining the logic of Fibonacci search.
Frequently Asked Questions (FAQ)
Here are some common questions about Fibonacci search:
Q1: What is Fibonacci search?
Fibonacci Search is an algorithm that uses Fibonacci numbers to divide the array and locate the target element efficiently.
Q2: Why use Fibonacci search instead of binary search?
It is especially useful when division operations are expensive, as it relies only on addition and subtraction.
Q3: Does the array need to be sorted?
Yes, Fibonacci search only works on sorted arrays.
Q4: What is the time complexity of Fibonacci search?
The time complexity is O(log n), similar to binary search, making it efficient for large datasets.
Q5: Can Fibonacci search be implemented recursively?
Yes, recursion can be applied, as shown in the recursive program, providing a modular and clean structure for implementation.
Conclusion
Fibonacci Search is an efficient and interesting search algorithm that combines mathematics and programming. In this article, we explored iterative, interactive, and recursive implementations in C++, showing how Fibonacci numbers help narrow down the search range before locating the exact element.
Beginners can benefit from practicing Fibonacci search to strengthen their understanding of algorithm design, recursive thinking, and how mathematical sequences can guide problem-solving in computer science. By experimenting with different arrays and keys, learners can explore how this elegant algorithm works in real-world applications.
