Searching is one of the most common tasks in programming, and knowing efficient search techniques can make your programs faster and smarter. While Linear Search checks every element and Binary Search splits the array in half, Ternary Search takes it a step further by dividing the array into three parts. This approach allows you to locate the target value even more efficiently, especially for large sorted datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is particularly useful in scenarios where data is sorted, and you want to minimize comparisons. It is used in computer science problems, optimization algorithms, and even in searching for maximum or minimum values in unimodal functions. For beginners, learning Ternary Search in PHP not only teaches a unique search method but also reinforces the concepts of recursion, loops, and step-wise logic. Understanding this algorithm builds a foundation for more advanced searching and optimization techniques.
Program 1: Basic Ternary Search Using Recursion
This program demonstrates the classic recursive Ternary Search approach to find a target value in a sorted array.
<?php
function ternarySearch($arr, $target, $left, $right) {
if ($right >= $left) {
$mid1 = $left + intval(($right - $left) / 3);
$mid2 = $right - intval(($right - $left) / 3);
if ($arr[$mid1] == $target) return $mid1;
if ($arr[$mid2] == $target) return $mid2;
if ($target < $arr[$mid1]) return ternarySearch($arr, $target, $left, $mid1 - 1);
elseif ($target > $arr[$mid2]) return ternarySearch($arr, $target, $mid2 + 1, $right);
else return ternarySearch($arr, $target, $mid1 + 1, $mid2 - 1);
}
return -1;
}
$array = [2, 4, 6, 8, 10, 12, 14];
$target = 10;
$index = ternarySearch($array, $target, 0, count($array) - 1);
if ($index != -1) echo "Element $target found at index $index using recursion.";
else echo "Element $target not found using recursion.";
?>This recursive approach divides the array into three parts and reduces the search space efficiently. Beginners can see how each recursive call focuses on a smaller segment, which helps in understanding divide-and-conquer strategies in programming.
Program 2: Ternary Search Wrapped in a Function
Here, we implement Ternary Search as a reusable function for better code modularity and readability.
<?php
function ternarySearchFunction($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($right >= $left) {
$mid1 = $left + intval(($right - $left) / 3);
$mid2 = $right - intval(($right - $left) / 3);
if ($arr[$mid1] == $target) return $mid1;
if ($arr[$mid2] == $target) return $mid2;
if ($target < $arr[$mid1]) $right = $mid1 - 1;
elseif ($target > $arr[$mid2]) $left = $mid2 + 1;
else { $left = $mid1 + 1; $right = $mid2 - 1; }
}
return -1;
}
$array = [1, 3, 5, 7, 9, 11, 13];
$target = 7;
$index = ternarySearchFunction($array, $target);
if ($index != -1) echo "Element $target found at index $index using function.";
else echo "Element $target not found using function.";
?>This iterative function version helps beginners learn modular coding. By wrapping the search logic in a function, the same method can be applied to multiple arrays and targets without rewriting code.
Program 3: Ternary Search for Strings
Ternary Search can also be applied to sorted arrays of strings. This example demonstrates searching for a name in alphabetical order.
<?php
function ternarySearchStrings($arr, $target, $left, $right) {
if ($right >= $left) {
$mid1 = $left + intval(($right - $left) / 3);
$mid2 = $right - intval(($right - $left) / 3);
if ($arr[$mid1] === $target) return $mid1;
if ($arr[$mid2] === $target) return $mid2;
if (strcmp($target, $arr[$mid1]) < 0) return ternarySearchStrings($arr, $target, $left, $mid1 - 1);
elseif (strcmp($target, $arr[$mid2]) > 0) return ternarySearchStrings($arr, $target, $mid2 + 1, $right);
else return ternarySearchStrings($arr, $target, $mid1 + 1, $mid2 - 1);
}
return -1;
}
$names = ["Albus", "Fred", "George", "Hermione", "Ron"];
$target = "Hermione";
$index = ternarySearchStrings($names, $target, 0, count($names) - 1);
if ($index != -1) echo "Name $target found at index $index.";
else echo "Name $target not found.";
?>This example shows that Ternary Search is not limited to numbers. Using strcmp allows comparisons between strings, making it useful for names, words, or any textual data in sorted arrays.
Program 4: Ternary Search for Multiple Occurrences
This program demonstrates how to find all occurrences of a target value in a sorted array using Ternary Search.
<?php
$array = [1, 2, 2, 2, 3, 4, 5];
$target = 2;
function ternarySearchOne($arr, $target, $left, $right) {
if ($right < $left) return -1;
$mid1 = $left + intval(($right - $left) / 3);
$mid2 = $right - intval(($right - $left) / 3);
if ($arr[$mid1] == $target) return $mid1;
if ($arr[$mid2] == $target) return $mid2;
if ($target < $arr[$mid1])
return ternarySearchOne($arr, $target, $left, $mid1 - 1);
elseif ($target > $arr[$mid2])
return ternarySearchOne($arr, $target, $mid2 + 1, $right);
else
return ternarySearchOne($arr, $target, $mid1 + 1, $mid2 - 1);
}
$index = ternarySearchOne($array, $target, 0, count($array) - 1);
if ($index == -1) {
echo "Element $target not found.";
exit;
}
$indices = [];
// expand left
$l = $index;
while ($l >= 0 && $array[$l] == $target) {
$indices[] = $l;
$l--;
}
// expand right
$r = $index + 1;
while ($r < count($array) && $array[$r] == $target) {
$indices[] = $r;
$r++;
}
sort($indices);
echo "Element $target found at indices: " . implode(", ", $indices) . ".";
?>This example teaches beginners how to handle duplicates while still leveraging the efficiency of Ternary Search. By storing all matching indices, it adapts the algorithm for real-world scenarios where multiple matches exist.
Program 5: Ternary Search with Error Handling
This program adds safety checks to ensure the array is sorted and prevents unnecessary errors.
<?php
function safeTernarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($right >= $left) {
$mid1 = $left + intval(($right - $left) / 3);
$mid2 = $right - intval(($right - $left) / 3);
if (!isset($arr[$mid1], $arr[$mid2])) return -1;
if ($arr[$mid1] == $target) return $mid1;
if ($arr[$mid2] == $target) return $mid2;
if ($target < $arr[$mid1]) $right = $mid1 - 1;
elseif ($target > $arr[$mid2]) $left = $mid2 + 1;
else { $left = $mid1 + 1; $right = $mid2 - 1; }
}
return -1;
}
$array = [3, 6, 9, 12, 15];
$target = 12;
$index = safeTernarySearch($array, $target);
if ($index != -1) echo "Element $target found at index $index safely.";
else echo "Element $target not found safely.";
?>Adding error handling teaches beginners how to write robust code while still using the Ternary Search logic. It emphasizes checking edge cases and preventing runtime errors.
Frequently Asked Questions (FAQ)
Ternary Search is a powerful technique but often raises beginner questions.
Q1: When should I use Ternary Search?
It works best for large, sorted arrays where minimizing comparisons is important.
Q2: Is Ternary Search faster than Binary Search?
It can be slightly faster in theory, but for practical purposes, both have logarithmic complexity.
Q3: Can Ternary Search work with strings?
Yes, with sorted string arrays and proper string comparison functions.
Q4: What is the time complexity of Ternary Search?
The time complexity is O(log₃ n), making it efficient for large datasets.
Q5: Can Ternary Search handle multiple occurrences?
Yes, by storing all matching indices, you can find every occurrence of the target.
Conclusion
Ternary Search is a useful and efficient algorithm for searching sorted arrays, dividing the array into three parts to locate a target. By practicing recursion, iterative functions, string handling, multiple occurrences, and error handling, beginners gain a solid understanding of the algorithm and its practical applications. These PHP examples make Ternary Search approachable and provide a strong foundation for more advanced search and optimization problems in real-world programming.
