Ternary Search is a searching algorithm designed to efficiently locate an element in a sorted array. Unlike Binary Search, which splits the array into two parts, Ternary Search divides the array into three sections. This approach can sometimes reduce the number of comparisons needed to find a target value. For beginners, Ternary Search is an excellent way to understand how dividing data into multiple parts can optimize searches while keeping the logic straightforward.
In practical terms, Ternary Search is most useful when dealing with large, sorted datasets where minimizing comparisons matters. It is applied in areas such as numerical analysis, data processing, and algorithm optimization, offering a clear way to explore the balance between algorithmic complexity and performance.
Program 1: Iterative Ternary Search
This program demonstrates Ternary Search using an iterative approach to find a target value in a sorted array of integers.
use strict;
use warnings;
my @arr = (2, 5, 8, 12, 16, 23, 38, 45, 56, 72);
my $target = 23;
sub ternary_search_iterative {
my ($arr_ref, $target) = @_;
my $low = 0;
my $high = scalar(@$arr_ref) - 1;
while ($low <= $high) {
my $mid1 = $low + int(($high - $low) / 3);
my $mid2 = $high - int(($high - $low) / 3);
if ($arr_ref->[$mid1] == $target) {
return $mid1;
}
if ($arr_ref->[$mid2] == $target) {
return $mid2;
}
if ($target < $arr_ref->[$mid1]) {
$high = $mid1 - 1;
} elsif ($target > $arr_ref->[$mid2]) {
$low = $mid2 + 1;
} else {
$low = $mid1 + 1;
$high = $mid2 - 1;
}
}
return -1;
}
my $index = ternary_search_iterative(\@arr, $target);
if ($index != -1) {
print "Element $target found at index $index\n";
} else {
print "Element $target not found\n";
}In this program, the array is split into three parts, and the target is compared to two middle points. Beginners can see how dividing the array reduces the number of comparisons compared to Linear Search, especially for large arrays.
Program 2: Recursive Ternary Search
This version uses recursion to implement Ternary Search, providing an alternative way to structure the logic.
use strict;
use warnings;
sub ternary_search_recursive {
my ($arr_ref, $low, $high, $target) = @_;
return -1 if $low > $high;
my $mid1 = $low + int(($high - $low) / 3);
my $mid2 = $high - int(($high - $low) / 3);
if ($arr_ref->[$mid1] == $target) {
return $mid1;
}
if ($arr_ref->[$mid2] == $target) {
return $mid2;
}
if ($target < $arr_ref->[$mid1]) {
return ternary_search_recursive($arr_ref, $low, $mid1 - 1, $target);
} elsif ($target > $arr_ref->[$mid2]) {
return ternary_search_recursive($arr_ref, $mid2 + 1, $high, $target);
} else {
return ternary_search_recursive($arr_ref, $mid1 + 1, $mid2 - 1, $target);
}
}
my @arr = (1, 3, 6, 9, 12, 15, 18, 21);
my $target = 15;
my $index = ternary_search_recursive(\@arr, 0, $#arr, $target);
if ($index != -1) {
print "Element $target found at index $index\n";
} else {
print "Element $target not found\n";
}The recursive approach highlights how breaking a problem into smaller parts can simplify the search logic. Beginners can practice understanding recursion and how the array segments are adjusted with each call.
Program 3: Ternary Search with Negative Numbers
Ternary Search also works with negative numbers, as long as the array is sorted.
use strict;
use warnings;
my @arr = (-50, -20, -10, 0, 10, 20, 50);
my $target = -10;
sub ternary_search {
my ($arr_ref, $low, $high, $target) = @_;
return -1 if $low > $high;
my $mid1 = $low + int(($high - $low)/3);
my $mid2 = $high - int(($high - $low)/3);
return $mid1 if $arr_ref->[$mid1] == $target;
return $mid2 if $arr_ref->[$mid2] == $target;
if ($target < $arr_ref->[$mid1]) {
return ternary_search($arr_ref, $low, $mid1 - 1, $target);
} elsif ($target > $arr_ref->[$mid2]) {
return ternary_search($arr_ref, $mid2 + 1, $high, $target);
} else {
return ternary_search($arr_ref, $mid1 + 1, $mid2 - 1, $target);
}
}
my $index = ternary_search(\@arr, 0, $#arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";Working with negative numbers shows beginners that comparisons, not absolute values, drive the search process, making Ternary Search versatile for any sorted numeric data.
Program 4: Ternary Search with Floating-Point Numbers
This example demonstrates searching in an array of decimal numbers, expanding the algorithm’s usefulness.
use strict;
use warnings;
my @arr = (0.5, 1.2, 2.3, 3.8, 4.5, 5.7);
my $target = 3.8;
sub ternary_search_fp {
my ($arr_ref, $low, $high, $target) = @_;
return -1 if $low > $high;
my $mid1 = $low + int(($high - $low)/3);
my $mid2 = $high - int(($high - $low)/3);
return $mid1 if $arr_ref->[$mid1] == $target;
return $mid2 if $arr_ref->[$mid2] == $target;
if ($target < $arr_ref->[$mid1]) {
return ternary_search_fp($arr_ref, $low, $mid1 - 1, $target);
} elsif ($target > $arr_ref->[$mid2]) {
return ternary_search_fp($arr_ref, $mid2 + 1, $high, $target);
} else {
return ternary_search_fp($arr_ref, $mid1 + 1, $mid2 - 1, $target);
}
}
my $index = ternary_search_fp(\@arr, 0, $#arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";For beginners, this demonstrates that Ternary Search is not limited to integers. Decimal values in sorted arrays can be searched with the same logic, making it suitable for scientific or financial data.
Program 5: Iterative Subroutine Ternary Search
Encapsulating the iterative approach in a subroutine simplifies usage across multiple datasets.
use strict;
use warnings;
sub ternary_search_sub {
my ($arr_ref, $target) = @_;
my $low = 0;
my $high = scalar(@$arr_ref) - 1;
while ($low <= $high) {
my $mid1 = $low + int(($high - $low)/3);
my $mid2 = $high - int(($high - $low)/3);
return $mid1 if $arr_ref->[$mid1] == $target;
return $mid2 if $arr_ref->[$mid2] == $target;
if ($target < $arr_ref->[$mid1]) {
$high = $mid1 - 1;
} elsif ($target > $arr_ref->[$mid2]) {
$low = $mid2 + 1;
} else {
$low = $mid1 + 1;
$high = $mid2 - 1;
}
}
return -1;
}
my @arr = (10, 20, 30, 40, 50, 60, 70);
my $target = 50;
my $index = ternary_search_sub(\@arr, $target);
print $index != -1 ? "Element $target found at index $index\n" : "Element $target not found\n";Using a subroutine makes it easy for beginners to reuse the search function without rewriting code for each dataset. It demonstrates modular programming while keeping the Ternary Search logic intact.
Frequently Asked Questions (FAQ)
Ternary Search is a step above simple searches, and beginners often have questions.
Q1. What is the time complexity of Ternary Search?
The time complexity is O(log₃ n), which can reduce comparisons compared to Binary Search for some datasets.
Q2. Can Ternary Search be used on unsorted arrays?
No, the array must be sorted. Sorting is essential for the algorithm to function properly.
Q3. How do I choose between Binary and Ternary Search?
Binary Search is simpler and slightly faster for most datasets, but Ternary Search shows a different approach to splitting the search space and can be a good learning tool.
Q4. Can Ternary Search handle negative and decimal numbers?
Yes, as long as the array is sorted, negative and floating-point numbers are supported.
Q5. Is recursion necessary for Ternary Search?
No, iterative implementations are common and may be easier for beginners to understand.
Conclusion
Ternary Search is an efficient algorithm for searching sorted arrays by dividing the data into three parts rather than two. This approach reduces the number of comparisons and demonstrates an important principle in algorithm design: breaking a problem into smaller segments can improve efficiency.
For beginners, practicing Ternary Search in Perl provides hands-on experience with both iterative and recursive techniques. It also reinforces essential programming concepts such as loops, subroutines, recursion, and handling negative or floating-point numbers. By experimenting with these examples, learners can build confidence and explore more advanced search and sorting algorithms in the future.
