Searching for an element efficiently is a core skill in programming. While Linear Search checks every element and Binary Search splits the array in half, Exponential Search offers a smart alternative for sorted arrays. This algorithm quickly finds a range where the target element might exist and then performs a Binary Search within that range. It’s especially useful for large datasets where the target is likely to be near the beginning of the array.
with hands-on learning.
get the skills and confidence to land your next move.
Exponential Search is used in computer science and practical applications like searching in sorted records, files, or databases. For beginners, learning Exponential Search helps understand how combining techniques—like range detection and Binary Search—can make algorithms faster and more efficient. Practicing this in PHP introduces important programming concepts such as loops, recursion, array indexing, and optimization, all in an approachable way.
Program 1: Basic Exponential Search Using Loops
This program demonstrates the standard Exponential Search approach, combining exponential range expansion and Binary Search.
<?php
function binarySearch($arr, $left, $right, $target) {
while ($left <= $right) {
$mid = intval($left + ($right - $left) / 2);
if ($arr[$mid] == $target) return $mid;
elseif ($arr[$mid] < $target) $left = $mid + 1;
else $right = $mid - 1;
}
return -1;
}
function exponentialSearch($arr, $target) {
$length = count($arr);
if ($arr[0] == $target) return 0;
$i = 1;
while ($i < $length && $arr[$i] <= $target) $i *= 2;
return binarySearch($arr, $i / 2, min($i, $length - 1), $target);
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 7;
$index = exponentialSearch($array, $target);
if ($index != -1) echo "Element $target found at index $index.";
else echo "Element $target not found.";
?>This program first finds a range by doubling the index until the target could be in the range, and then uses Binary Search to pinpoint its exact position. Beginners can see how combining simple algorithms improves efficiency compared to Linear Search.
Program 2: Exponential Search as a Reusable Function
Wrapping Exponential Search in a function makes it reusable for multiple arrays and targets.
<?php
function exponentialSearchFunction($arr, $target) {
$length = count($arr);
if ($arr[0] == $target) return 0;
$i = 1;
while ($i < $length && $arr[$i] <= $target) $i *= 2;
$left = intval($i / 2);
$right = min($i, $length - 1);
while ($left <= $right) {
$mid = intval($left + ($right - $left) / 2);
if ($arr[$mid] == $target) return $mid;
elseif ($arr[$mid] < $target) $left = $mid + 1;
else $right = $mid - 1;
}
return -1;
}
$array = [2, 4, 6, 8, 10, 12, 14];
$target = 10;
$index = exponentialSearchFunction($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 makes the code reusable. Beginners learn modular programming and how to combine range detection with a standard search efficiently.
Program 3: Exponential Search Using Recursion
Exponential Search can also be implemented recursively, combining recursive Binary Search after range detection.
<?php
function binarySearchRecursive($arr, $left, $right, $target) {
if ($right >= $left) {
$mid = intval($left + ($right - $left) / 2);
if ($arr[$mid] == $target) return $mid;
if ($arr[$mid] > $target) return binarySearchRecursive($arr, $left, $mid - 1, $target);
return binarySearchRecursive($arr, $mid + 1, $right, $target);
}
return -1;
}
function exponentialSearchRecursive($arr, $target, $i = 1) {
if ($arr[0] == $target) return 0;
$length = count($arr);
if ($i >= $length || $arr[$i] > $target) return binarySearchRecursive($arr, intval($i / 2), min($i, $length - 1), $target);
return exponentialSearchRecursive($arr, $target, $i * 2);
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 11;
$index = exponentialSearchRecursive($array, $target);
if ($index != -1) echo "Element $target found at index $index using recursion.";
else echo "Element $target not found using recursion.";
?>This recursive approach helps beginners understand how recursion can simplify dividing the search space. The algorithm is still efficient, but the recursive style is easier to follow for conceptual understanding.
Program 4: Exponential Search for Strings
Exponential Search can also be adapted for sorted arrays of strings, useful for names or words.
<?php
function binarySearchStrings($arr, $left, $right, $target) {
while ($left <= $right) {
$mid = intval($left + ($right - $left) / 2);
if ($arr[$mid] === $target) return $mid;
elseif (strcmp($arr[$mid], $target) < 0) $left = $mid + 1;
else $right = $mid - 1;
}
return -1;
}
function exponentialSearchStrings($arr, $target) {
if ($arr[0] === $target) return 0;
$i = 1;
$length = count($arr);
while ($i < $length && strcmp($arr[$i], $target) <= 0) $i *= 2;
return binarySearchStrings($arr, intval($i / 2), min($i, $length - 1), $target);
}
$names = ["Albus", "Fred", "George", "Hermione", "Ron"];
$target = "Hermione";
$index = exponentialSearchStrings($names, $target);
if ($index != -1) echo "Name $target found at index $index.";
else echo "Name $target not found.";
?>This example shows that Exponential Search can handle textual data by using string comparison functions like strcmp. Beginners learn that the same algorithm can be adapted to different types of sorted data.
Program 5: Exponential Search for Multiple Occurrences
This program demonstrates how to locate all occurrences of a target value using Exponential Search.
<?php
$array = [2, 4, 4, 4, 6, 8, 10];
$target = 4;
function exponentialSearchAll($arr, $target) {
$n = count($arr);
$result = [];
if ($n === 0) return $result;
// quick check first element
if ($arr[0] === $target) {
$found = 0;
} else {
// find range [left, right]
$i = 1;
while ($i < $n && $arr[$i] <= $target) {
$i *= 2;
}
$left = intval($i / 2);
$right = min($i, $n - 1);
// find any one index of target in that range
$found = -1;
for ($j = $left; $j <= $right; $j++) {
if ($arr[$j] === $target) {
$found = $j;
break;
}
}
if ($found === -1) return $result; // not found
}
// expand from found index to collect all duplicates
$l = $found;
while ($l - 1 >= 0 && $arr[$l - 1] === $target) $l--;
$r = $found;
while ($r + 1 < $n && $arr[$r + 1] === $target) $r++;
for ($k = $l; $k <= $r; $k++) $result[] = $k;
return $result;
}
$indices = exponentialSearchAll($array, $target);
if (!empty($indices)) {
echo "Element $target found at indices: " . implode(", ", $indices) . ".";
} else {
echo "Element $target not found.";
}
?>This example shows how to adapt Exponential Search to find duplicates, making it practical for real-world scenarios. Beginners can see how combining range detection and linear checks works effectively.
Frequently Asked Questions (FAQ)
Exponential Search is a practical and efficient search method, but beginners often have questions.
Q1: When should I use Exponential Search?
It is best for large sorted arrays, especially when the target is near the beginning.
Q2: How does Exponential Search compare to Binary Search?
It quickly finds the range before using Binary Search, which can reduce comparisons in some cases.
Q3: Can Exponential Search work with strings?
Yes, using string comparison functions like strcmp for sorted textual data.
Q4: What is the time complexity of Exponential Search?
The time complexity is O(log n) for Binary Search within the detected range, with O(log i) for range detection.
Q5: Can Exponential Search find multiple occurrences?
Yes, by scanning the identified range, all duplicates can be located efficiently.
Conclusion
Exponential Search is an efficient and beginner-friendly algorithm for searching sorted arrays. By combining exponential range detection with Binary Search, it provides fast results while remaining easy to understand. These PHP examples—using loops, recursion, strings, and multiple occurrences—make Exponential Search approachable and practical for real-world programming. Practicing this algorithm helps beginners grasp search optimization, recursion, and array traversal, preparing them for more advanced data handling tasks.
