Searching for a value in a sorted array is a fundamental task in programming, and there are many techniques to do it efficiently. While Binary Search and Exponential Search are widely known, Fibonacci Search provides a unique approach by using Fibonacci numbers to split the array into sections. This method helps reduce the number of comparisons and can be especially useful for large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is used in computer science, optimization problems, and even in situations where data access costs vary. For beginners, learning Fibonacci Search in PHP introduces an exciting mix of mathematics and programming logic. It also reinforces concepts such as array traversal, loops, recursion, and algorithm efficiency, making it a practical addition to your coding toolkit.
Program 1: Basic Fibonacci Search Using Loops
This program demonstrates a standard Fibonacci Search to locate a target value in a sorted array using iterative logic.
<?php
function fibonacciSearch($arr, $target) {
$length = count($arr);
$fibMMm2 = 0;
$fibMMm1 = 1;
$fibM = $fibMMm2 + $fibMMm1;
while ($fibM < $length) {
$fibMMm2 = $fibMMm1;
$fibMMm1 = $fibM;
$fibM = $fibMMm2 + $fibMMm1;
}
$offset = -1;
while ($fibM > 1) {
$i = min($offset + $fibMMm2, $length - 1);
if ($arr[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elseif ($arr[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else return $i;
}
if ($fibMMm1 && isset($arr[$offset + 1]) && $arr[$offset + 1] == $target) return $offset + 1;
return -1;
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 7;
$index = fibonacciSearch($array, $target);
if ($index != -1) echo "Element $target found at index $index.";
else echo "Element $target not found.";
?>This program calculates Fibonacci numbers to determine sections of the array to compare with the target. Beginners can observe how the search space is reduced efficiently, similar to Binary Search but with a Fibonacci-based approach.
Program 2: Fibonacci Search Wrapped in a Function
By encapsulating Fibonacci Search into a function, the search becomes reusable for different arrays and target values.
<?php
function fibonacciSearchFunction($arr, $target) {
$n = count($arr);
$fibMMm2 = 0;
$fibMMm1 = 1;
$fibM = $fibMMm2 + $fibMMm1;
while ($fibM < $n) {
$fibMMm2 = $fibMMm1;
$fibMMm1 = $fibM;
$fibM = $fibMMm2 + $fibMMm1;
}
$offset = -1;
while ($fibM > 1) {
$i = min($offset + $fibMMm2, $n - 1);
if ($arr[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elseif ($arr[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else return $i;
}
if ($fibMMm1 && isset($arr[$offset + 1]) && $arr[$offset + 1] == $target) return $offset + 1;
return -1;
}
$array = [2, 4, 6, 8, 10, 12, 14];
$target = 10;
$index = fibonacciSearchFunction($array, $target);
if ($index != -1) echo "Element $target found at index $index using function.";
else echo "Element $target not found using function.";
?>Using a function improves readability and allows repeated use without rewriting the search logic. Beginners can practice modular programming and understand how combining loops with Fibonacci calculations creates an efficient search.
Program 3: Fibonacci Search Using Recursion
This program shows a recursive approach, integrating Fibonacci numbers and recursive calls to locate the target value.
<?php
function fibonacciSearchRecursive($arr, $target, $fibM, $fibMMm1, $fibMMm2, $offset = -1) {
if ($fibM <= 1) {
if ($fibMMm1 && isset($arr[$offset + 1]) && $arr[$offset + 1] == $target) return $offset + 1;
return -1;
}
$i = min($offset + $fibMMm2, count($arr) - 1);
if ($arr[$i] < $target) return fibonacciSearchRecursive($arr, $target, $fibMMm1, $fibMMm2, $fibM - $fibMMm1, $i);
elseif ($arr[$i] > $target) return fibonacciSearchRecursive($arr, $target, $fibMMm2, $fibMMm1 - $fibMMm2, $fibM - $fibMMm1, $offset);
else return $i;
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 11;
$fibMMm2 = 0;
$fibMMm1 = 1;
$fibM = $fibMMm2 + $fibMMm1;
while ($fibM < count($array)) {
$fibMMm2 = $fibMMm1;
$fibMMm1 = $fibM;
$fibM = $fibMMm2 + $fibMMm1;
}
$index = fibonacciSearchRecursive($array, $target, $fibM, $fibMMm1, $fibMMm2);
if ($index != -1) echo "Element $target found at index $index using recursion.";
else echo "Element $target not found using recursion.";
?>This recursive version helps beginners understand the logic behind Fibonacci Search while introducing them to recursive problem-solving. The range selection and Fibonacci calculation are clear through the function parameters.
Program 4: Fibonacci Search for Strings
Fibonacci Search can also be adapted for sorted string arrays, which is useful for names or words.
<?php
function fibonacciSearchStrings($arr, $target) {
$n = count($arr);
$fibMMm2 = 0;
$fibMMm1 = 1;
$fibM = $fibMMm2 + $fibMMm1;
while ($fibM < $n) {
$fibMMm2 = $fibMMm1;
$fibMMm1 = $fibM;
$fibM = $fibMMm2 + $fibMMm1;
}
$offset = -1;
while ($fibM > 1) {
$i = min($offset + $fibMMm2, $n - 1);
$cmp = strcmp($arr[$i], $target);
if ($cmp < 0) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
} elseif ($cmp > 0) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
} else return $i;
}
if ($fibMMm1 && isset($arr[$offset + 1]) && $arr[$offset + 1] === $target) return $offset + 1;
return -1;
}
$names = ["Albus", "Fred", "George", "Hermione", "Ron"];
$target = "Hermione";
$index = fibonacciSearchStrings($names, $target);
if ($index != -1) echo "Name $target found at index $index.";
else echo "Name $target not found.";
?>Using strcmp allows Fibonacci Search to compare strings effectively, making it practical for textual data like names and words. Beginners can see how to adapt number-based algorithms to strings.
Program 5: Fibonacci Search for Multiple Occurrences
This program demonstrates finding all occurrences of a target value using Fibonacci Search.
<?php
$array = [2, 4, 4, 4, 6, 8, 10];
$target = 4;
function fibonacciSearchOne($arr, $target) {
$n = count($arr);
$fibMMm2 = 0;
$fibMMm1 = 1;
$fibM = $fibMMm2 + $fibMMm1;
while ($fibM < $n) {
$fibMMm2 = $fibMMm1;
$fibMMm1 = $fibM;
$fibM = $fibMMm2 + $fibMMm1;
}
$offset = -1;
while ($fibM > 1) {
$i = min($offset + $fibMMm2, $n - 1);
if ($arr[$i] < $target) {
$fibM = $fibMMm1;
$fibMMm1 = $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
$offset = $i;
}
elseif ($arr[$i] > $target) {
$fibM = $fibMMm2;
$fibMMm1 = $fibMMm1 - $fibMMm2;
$fibMMm2 = $fibM - $fibMMm1;
}
else {
return $i; // found one index
}
}
if ($fibMMm1 && $offset + 1 < $n && $arr[$offset + 1] == $target)
return $offset + 1;
return -1;
}
function fibonacciSearchAll($arr, $target) {
$n = count($arr);
$result = [];
$index = fibonacciSearchOne($arr, $target);
if ($index == -1) return $result;
// expand left
$l = $index;
while ($l >= 0 && $arr[$l] == $target) {
$result[] = $l;
$l--;
}
// expand right
$r = $index + 1;
while ($r < $n && $arr[$r] == $target) {
$result[] = $r;
$r++;
}
sort($result);
return $result;
}
$indices = fibonacciSearchAll($array, $target);
if (!empty($indices))
echo "Element $target found at indices: " . implode(", ", $indices) . ".";
else
echo "Element $target not found.";
?>This shows how Fibonacci Search can be extended to locate duplicates in a sorted array. Beginners learn to combine range detection and linear checks to handle real-world scenarios efficiently.
Frequently Asked Questions (FAQ)
Fibonacci Search is efficient but often raises beginner questions.
Q1: When should I use Fibonacci Search?
It is best for large sorted arrays where minimizing comparisons is important.
Q2: How does Fibonacci Search differ from Binary Search?
It uses Fibonacci numbers to divide the array instead of splitting exactly in half, which can reduce comparisons in certain cases.
Q3: Can Fibonacci Search work with strings?
Yes, by using string comparison functions like strcmp.
Q4: What is the time complexity of Fibonacci Search?
The time complexity is O(log n), similar to Binary Search, with efficient range detection.
Q5: Can Fibonacci Search handle multiple occurrences?
Yes, by scanning the relevant range, all duplicates can be found efficiently.
Conclusion
Fibonacci Search is a unique and efficient method for searching sorted arrays. By leveraging Fibonacci numbers to determine search sections, it reduces comparisons while remaining simple to implement. The PHP examples—using loops, recursion, strings, and multiple occurrences—make the algorithm approachable and practical. Practicing Fibonacci Search helps beginners strengthen array traversal skills, understand mathematical patterns in algorithms, and prepare for more advanced programming challenges.
