Fibonacci Search is an efficient algorithm for finding elements in a sorted array. It is based on the Fibonacci sequence, which helps determine the range for searching by splitting the array into sections according to Fibonacci numbers. This method is especially useful for large datasets where linear search would be too slow, and it provides an alternative to Binary Search with some advantages in specific scenarios. For beginners, it’s a great way to explore how mathematical sequences can be applied to practical programming problems.
The algorithm works by comparing the target element with values in the array located at positions derived from Fibonacci numbers. By reducing the search space in Fibonacci-sized chunks, it can quickly narrow down the location of the element. Fibonacci Search is used in areas such as database lookups, computer memory optimization, and algorithm design challenges, making it a practical and interesting tool to learn for any Perl programmer.
Program 1: Basic Fibonacci Search
This program demonstrates a straightforward implementation of Fibonacci Search for a predefined sorted array of integers.
use strict;
use warnings;
my @arr = (10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100);
my $target = 85;
sub fibonacci_search {
my ($arr_ref, $target) = @_;
my $n = scalar(@$arr_ref);
my ($fibMMm2, $fibMMm1, $fibM) = (0, 1, 1);
while ($fibM < $n) {
($fibMMm2, $fibMMm1, $fibM) = ($fibMMm1, $fibM, $fibMMm1 + $fibM);
}
my $offset = -1;
while ($fibM > 1) {
my $i = ($offset + $fibMMm2) < $n-1 ? $offset + $fibMMm2 : $n-1;
if ($arr_ref->[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elsif ($arr_ref->[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else {
return $i;
}
}
return ($fibMMm1 && $arr_ref->[$offset + 1] == $target) ? $offset + 1 : -1;
}
my $index = fibonacci_search(\@arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";In this example, Fibonacci Search identifies a suitable position for the target by using Fibonacci numbers to narrow the search. It is particularly useful for beginners to understand alternative ways of partitioning arrays compared to binary or linear search.
Program 2: Recursive Fibonacci Search
This version of Fibonacci Search demonstrates how recursion can be used to implement the search logic cleanly.
use strict;
use warnings;
my @arr = (5, 10, 15, 20, 25, 30, 35, 40);
sub fibonacci {
my $n = shift;
return $n if $n < 2;
return fibonacci($n - 1) + fibonacci($n - 2);
}
sub fibonacci_search_recursive {
my ($arr_ref, $target, $fibM, $offset) = @_;
return -1 if $fibM == 0;
my $i = ($offset + $fibM - 1) < $#$arr_ref ? $offset + $fibM - 1 : $#$arr_ref;
if ($arr_ref->[$i] == $target) {
return $i;
} elsif ($arr_ref->[$i] > $target) {
return fibonacci_search_recursive($arr_ref, $target, $fibM - 1, $offset);
} else {
return fibonacci_search_recursive($arr_ref, $target, $fibM - 2, $i + 1);
}
}
my $fibM = 1;
$fibM++ while fibonacci($fibM) < scalar(@arr);
my $target = 30;
my $index = fibonacci_search_recursive(\@arr, $target, fibonacci($fibM), -1);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";Using recursion simplifies understanding how the search progresses through Fibonacci segments. Beginners can see how the algorithm reduces the problem step by step without explicit loops.
Program 3: Fibonacci Search with Negative Numbers
This example demonstrates searching within arrays containing negative integers.
use strict;
use warnings;
my @arr = (-50, -20, -10, 0, 10, 20, 30);
my $target = -10;
sub fibonacci_search {
my ($arr_ref, $target) = @_;
my $n = scalar(@$arr_ref);
my ($fibMMm2, $fibMMm1, $fibM) = (0, 1, 1);
while ($fibM < $n) {
($fibMMm2, $fibMMm1, $fibM) = ($fibMMm1, $fibM, $fibMMm1 + $fibM);
}
my $offset = -1;
while ($fibM > 1) {
my $i = ($offset + $fibMMm2) < $n-1 ? $offset + $fibMMm2 : $n-1;
if ($arr_ref->[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elsif ($arr_ref->[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else {
return $i;
}
}
return ($fibMMm1 && $arr_ref->[$offset + 1] == $target) ? $offset + 1 : -1;
}
my $index = fibonacci_search(\@arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";The search works the same way with negative numbers because the comparison logic is consistent. It shows beginners that Fibonacci Search only requires a sorted array, not positive-only values.
Program 4: Fibonacci Search with Floating-Point Numbers
Fibonacci Search can also be applied to arrays containing decimal values.
use strict;
use warnings;
my @arr = (0.5, 1.2, 2.8, 3.3, 4.5, 5.7);
my $target = 3.3;
sub fibonacci_search {
my ($arr_ref, $target) = @_;
my $n = scalar(@$arr_ref);
my ($fibMMm2, $fibMMm1, $fibM) = (0, 1, 1);
while ($fibM < $n) {
($fibMMm2, $fibMMm1, $fibM) = ($fibMMm1, $fibM, $fibMMm1 + $fibM);
}
my $offset = -1;
while ($fibM > 1) {
my $i = ($offset + $fibMMm2) < $n-1 ? $offset + $fibMMm2 : $n-1;
if ($arr_ref->[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elsif ($arr_ref->[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else {
return $i;
}
}
return ($fibMMm1 && $arr_ref->[$offset + 1] == $target) ? $offset + 1 : -1;
}
my $index = fibonacci_search(\@arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";This shows the flexibility of the algorithm. As long as the array is sorted, Fibonacci Search can handle decimal numbers in addition to integers.
Program 5: Reusable Subroutine for Fibonacci Search
Encapsulating the algorithm in a subroutine makes it easy to apply to different arrays and targets.
use strict;
use warnings;
sub fibonacci_search {
my ($arr_ref, $target) = @_;
my $n = scalar @$arr_ref;
# Initialize Fibonacci numbers
my ($fibMm2, $fibMm1) = (0, 1); # fib(M-2) and fib(M-1)
my $fibM = $fibMm2 + $fibMm1; # fib(M)
# Generate the smallest Fibonacci number >= n
while ($fibM < $n) {
($fibMm2, $fibMm1) = ($fibMm1, $fibM);
$fibM = $fibMm1 + $fibMm2;
}
my $offset = -1;
# While there are elements to be inspected
while ($fibM > 1) {
my $i = ($offset + $fibMm2 < $n - 1) ? $offset + $fibMm2 : $n - 1;
if ($arr_ref->[$i] < $target) {
$fibM = $fibMm1;
$fibMm1 = $fibMm2;
$fibMm2 = $fibM - $fibMm1;
$offset = $i;
}
elsif ($arr_ref->[$i] > $target) {
$fibM = $fibMm2;
$fibMm1 -= $fibMm2;
$fibMm2 = $fibM - $fibMm1;
}
else {
return $i; # Target found
}
}
# Check if the last element is the target
return ($fibMm1 && $arr_ref->[$offset + 1] == $target) ? $offset + 1 : -1;
}
# Example usage
my @arr = (1, 3, 5, 7, 9, 11, 13);
my $target = 9;
my $index = fibonacci_search(\@arr, $target);
if ($index != -1) {
print "Element $target found at index $index\n";
} else {
print "Element $target not found\n";
}This reusable subroutine is ideal for beginners to practice calling the same algorithm with different datasets and targets, promoting modular coding habits.
Frequently Asked Questions (FAQ)
Fibonacci Search can raise questions for beginners who are exploring efficient searching methods.
Q1. What is the time complexity of Fibonacci Search?
The algorithm has a time complexity of O(log n), similar to Binary Search, but it uses Fibonacci numbers to determine the range.
Q2. Can Fibonacci Search work on unsorted arrays?
No, the array must be sorted, as the algorithm relies on ordered values to divide the search space correctly.
Q3. Does Fibonacci Search work with negative numbers and decimals?
Yes, it works with any sorted numerical array, whether integers or floating-point numbers, positive or negative.
Q4. Why choose Fibonacci Search over Binary Search?
It can provide slightly better performance in certain cases where the data is accessed sequentially or in memory structures aligned with Fibonacci intervals.
Q5. Is recursion required for Fibonacci Search?
Recursion is optional. Both iterative and recursive implementations are valid, depending on programming style and clarity.
Conclusion
Fibonacci Search is a fascinating algorithm that combines mathematical insight with practical programming. It efficiently searches sorted arrays by splitting them according to Fibonacci numbers and provides a strong alternative to Binary Search.
Beginners can benefit from implementing Fibonacci Search in Perl because it teaches algorithmic thinking, recursion, modular coding, and handling different types of data such as negative numbers and floating-point values. By experimenting with the examples provided, learners can gain confidence and deepen their understanding of searching algorithms in programming.
