Searching is an essential operation in programming, and efficient searching algorithms can make a big difference in performance, especially when working with large datasets. One fascinating method is Fibonacci Search, which combines the principles of the Fibonacci sequence with searching in sorted arrays. This algorithm is similar to Binary Search but uses Fibonacci numbers to divide the array, offering a unique and sometimes more efficient way to locate an element.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is particularly useful when you want a divide-and-conquer approach without always splitting the array exactly in half. By using Fibonacci numbers to determine positions, it provides a flexible search pattern and reduces the number of comparisons. Beginners will find implementing Fibonacci Search in C an excellent exercise in understanding both mathematical sequences and practical programming techniques.
Program 1: Iterative Fibonacci Search
The first program demonstrates Fibonacci Search using an iterative approach. This version is straightforward, making it easier for beginners to follow the logic of the algorithm.
#include <stdio.h>
// Function to find the minimum of two numbers
int min(int x, int y) {
return (x <= y) ? x : y;
}
int fibonacciSearch(int arr[], int n, int key) {
int fibMMm2 = 0; // (m-2)'th Fibonacci number
int fibMMm1 = 1; // (m-1)'th Fibonacci number
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci number
// Find the smallest Fibonacci number greater than or equal to n
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; // Element found
}
}
if (fibMMm1 && arr[offset + 1] == key)
return offset + 1;
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
printf("Enter the element to search: ");
scanf("%d", &key);
int index = fibonacciSearch(arr, n, key);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found in the array\n", key);
return 0;
}In this iterative version, the algorithm first finds the smallest Fibonacci number greater than or equal to the array size. Then it uses the Fibonacci sequence to check elements at calculated positions. If the key is larger than the current element, the search moves ahead, reducing the search range using Fibonacci numbers. Beginners can appreciate how the Fibonacci sequence is applied practically, making the algorithm a blend of math and programming.
Program 2: Recursive Fibonacci Search
Fibonacci Search can also be implemented recursively, which provides a good exercise in recursion and algorithmic thinking. This approach is slightly more advanced but elegant for understanding divide-and-conquer strategies.
#include <stdio.h>
int min(int x, int y) {
return (x <= y) ? x : y;
}
/*
Recursive Fibonacci Search.
Parameters:
- arr: sorted array
- key: value to search
- offset: eliminated range offset (initially -1)
- fibMMm2: (m-2)'th Fibonacci number
- fibMMm1: (m-1)'th Fibonacci number
- fibM: m'th Fibonacci number
- n: array size
*/
int fibonacciSearchRecursive(int arr[], int key, int offset,
int fibMMm2, int fibMMm1, int fibM, int n) {
if (fibM <= 1) {
if (fibMMm1 && (offset + 1) < n && arr[offset + 1] == key)
return offset + 1;
return -1;
}
int i = min(offset + fibMMm2, n - 1);
if (arr[i] == key)
return i;
if (arr[i] < key) {
// Move to right subarray:
// new fibM = fibMMm1
// new fibMMm1 = fibMMm2
// new fibMMm2 = new fibM - new fibMMm1 (which equals old fibMMm1 - old fibMMm2)
int new_fibM = fibMMm1;
int new_fibMMm1 = fibMMm2;
int new_fibMMm2 = new_fibM - new_fibMMm1;
return fibonacciSearchRecursive(arr, key, i,
new_fibMMm2, new_fibMMm1, new_fibM, n);
} else {
// Move to left subarray:
// new fibM = fibMMm2
// new fibMMm1 = fibMMm1 - fibMMm2
// new fibMMm2 = new fibM - new fibMMm1
int new_fibM = fibMMm2;
int new_fibMMm1 = fibMMm1 - fibMMm2;
int new_fibMMm2 = new_fibM - new_fibMMm1;
return fibonacciSearchRecursive(arr, key, offset,
new_fibMMm2, new_fibMMm1, new_fibM, n);
}
}
int main() {
int arr[] = {5, 15, 25, 35, 45, 55, 65, 75, 85};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
printf("Enter the element to search: ");
scanf("%d", &key);
// Calculate initial Fibonacci numbers: smallest fibM >= n
int fibMMm2 = 0, fibMMm1 = 1, fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int index = fibonacciSearchRecursive(arr, key, -1, fibMMm2, fibMMm1, fibM, n);
if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found in the array\n", key);
return 0;
}In the recursive version, the function continually recalculates the Fibonacci numbers to narrow down the search space. Each recursive call focuses on a smaller segment, guided by the Fibonacci sequence. Beginners will see how recursion can replace loops, and how the mathematical pattern of Fibonacci numbers directs the search efficiently.
Frequently Asked Questions (FAQ)
Here are some common questions about Fibonacci Search:
What is the time complexity of Fibonacci Search?
Fibonacci Search has a time complexity of O(log n), similar to Binary Search, but it uses Fibonacci numbers instead of halving the array.
Is Fibonacci Search better than Binary Search?
It depends on the dataset. Fibonacci Search is particularly useful for sequential access data structures or when memory access is slow, as it can reduce jumps and comparisons in some cases.
Does Fibonacci Search require sorted arrays?
Yes, the array must be sorted for the algorithm to work correctly. The Fibonacci positions assume a sorted order.
Can Fibonacci Search be used with floating-point numbers?
Yes, as long as the array is sorted, the algorithm can be adapted to work with floating-point numbers.
Why use Fibonacci numbers in search?
Fibonacci numbers provide a natural way to divide the array non-uniformly, which can be more efficient in some sequential memory or storage scenarios.
Conclusion
Fibonacci Search is a powerful searching algorithm that combines the beauty of the Fibonacci sequence with practical programming. By using Fibonacci numbers to estimate positions, it offers an efficient alternative to traditional Binary Search, especially for sequential data or memory-constrained environments.
The iterative and recursive examples above illustrate both how the algorithm works and how it can be implemented in C. Beginners can benefit from practicing both approaches, experimenting with arrays of different sizes, and understanding how mathematical sequences can guide efficient algorithms. Mastering Fibonacci Search not only improves your coding skills but also strengthens your problem-solving and algorithmic thinking.
