Searching efficiently in a sorted array is a fundamental skill for any programmer. While Binary Search is widely taught and used, Fibonacci Search offers an alternative approach that can be more efficient in certain scenarios. Fibonacci Search leverages Fibonacci numbers to divide the array into sections, helping to locate the target element with minimal comparisons. This makes it a useful algorithm for large sorted arrays or when computational efficiency is important.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is especially relevant in scenarios where addition operations are cheaper than division operations, such as in embedded systems or older computing environments. Learning Fibonacci Search gives beginners insight into mathematical approaches to searching and introduces a new way to think about indexing and range selection in arrays.
Program 1: Fibonacci Search Using Loop
This program demonstrates the standard Fibonacci Search on a sorted array of integers. It finds the position of a target element by calculating Fibonacci numbers and reducing the search range iteratively.
using System;
class Program
{
static int FibonacciSearch(int[] arr, int key)
{
int n = arr.Length;
int fibMMm2 = 0; // (m-2)'th Fibonacci number
int fibMMm1 = 1; // (m-1)'th Fibonacci number
int fibM = fibMMm2 + fibMMm1;
while (fibM < n)
{
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1)
{
int i = Math.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 == 1 && arr[offset + 1] == key)
return offset + 1;
return -1;
}
static void Main()
{
int[] numbers = { 10, 22, 35, 40, 45, 50, 80, 82, 85 };
int target = 40;
int result = FibonacciSearch(numbers, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This program works by calculating Fibonacci numbers to determine indices for comparisons. It is a useful exercise for beginners to understand how mathematical sequences can guide search algorithms efficiently.
Program 2: Recursive Fibonacci Search
The recursive version of Fibonacci Search uses the same principles but applies them through recursion, making it easier to see how the problem is broken down into smaller subarrays.
using System;
class Program
{
static int FibonacciSearchRecursive(int[] arr, int key, int offset, int fibM, int fibMMm1, int fibMMm2)
{
if (fibM == 0)
return -1;
int i = Math.Min(offset + fibMMm2, arr.Length - 1);
if (arr[i] == key)
return i;
if (arr[i] < key)
return FibonacciSearchRecursive(arr, key, i, fibMMm1, fibMMm2, fibMMm1 - fibMMm2);
else
return FibonacciSearchRecursive(arr, key, offset, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2));
}
static int FibonacciSearchStart(int[] arr, int key)
{
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm1 + fibMMm2;
while (fibM < arr.Length)
{
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
return FibonacciSearchRecursive(arr, key, -1, fibM, fibMMm1, fibMMm2);
}
static void Main()
{
int[] numbers = { 5, 10, 15, 20, 25, 30 };
int target = 25;
int result = FibonacciSearchStart(numbers, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This recursive version is helpful for beginners to visualize the reduction of the search space and how recursive calls handle different segments of the array.
Program 3: Fibonacci Search with Floating-Point Numbers
Fibonacci Search can also work with sorted arrays of floating-point numbers, which is useful in scientific computing or financial calculations.
using System;
class Program
{
static int FibonacciSearchFloat(double[] arr, double key)
{
int n = arr.Length;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm1 + fibMMm2;
while (fibM < n)
{
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int offset = -1;
while (fibM > 1)
{
int i = Math.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 == 1 && Math.Abs(arr[offset + 1] - key) < 1e-9)
return offset + 1;
return -1;
}
static void Main()
{
double[] numbers = { 1.5, 3.2, 5.1, 7.4, 9.8 };
double target = 7.4;
int result = FibonacciSearchFloat(numbers, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This program demonstrates the flexibility of Fibonacci Search, showing that it is not limited to integers but works for any comparable type.
Program 4: Fibonacci Search on Strings
Fibonacci Search can also be applied to sorted string arrays using lexicographical comparison. This is useful in applications like name directories or sorted lists of words.
using System;
class Program
{
static int FibonacciSearchString(string[] arr, string key)
{
int n = arr.Length;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm1 + fibMMm2;
while (fibM < n)
{
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int offset = -1;
while (fibM > 1)
{
int i = Math.Min(offset + fibMMm2, n - 1);
int cmp = string.Compare(arr[i], key);
if (cmp < 0)
{
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}
else if (cmp > 0)
{
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
else
return i;
}
if (fibMMm1 == 1 && arr[offset + 1] == key)
return offset + 1;
return -1;
}
static void Main()
{
string[] names = { "Alice", "Bob", "Charlie", "Diana", "Edward" };
string target = "Charlie";
int result = FibonacciSearchString(names, target);
if (result != -1)
Console.WriteLine($"Element {target} found at index {result}");
else
Console.WriteLine($"Element {target} not found in the array");
}
}This version emphasizes real-world applications where searching through a sorted array of strings is common, such as databases, contact lists, or directories.
Frequently Asked Questions (FAQ)
Q1: What is Fibonacci Search best used for?
It’s ideal for large, sorted arrays where you want to minimize comparisons using Fibonacci sequence-based indexing.
Q2: How does Fibonacci Search differ from Binary Search?
Instead of splitting arrays exactly in half, Fibonacci Search uses Fibonacci numbers to split the array, which may reduce some calculations in specific hardware scenarios.
Q3: What is the time complexity of Fibonacci Search?
The time complexity is O(log n), similar to Binary Search, but it often requires fewer comparisons in practice.
Q4: Can Fibonacci Search work on strings or floating-point numbers?
Yes, it works on any sorted array of comparable types, including integers, floats, and strings.
Conclusion
Fibonacci Search is a powerful and flexible search algorithm that combines mathematical reasoning with efficient search strategies. By practicing with integers, floats, strings, loops, and recursion, beginners can strengthen their understanding of searching in sorted arrays. Exploring Fibonacci Search alongside other algorithms like Binary Search and Exponential Search helps you build a solid foundation in efficient data handling.
