Searching efficiently in large datasets is a key skill for every programmer, and while Binary Search is widely known, there’s another algorithm called Ternary Search that divides the search space into three parts instead of two. Ternary Search works on sorted arrays and repeatedly splits the array into three segments to determine which segment contains the target. By reducing the search space more aggressively than Binary Search, it can sometimes provide faster results in specific cases.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is especially useful in applications where a function is unimodal, meaning it has a single peak or maximum, such as optimization problems, or when searching in sorted numeric datasets. For beginners, implementing Ternary Search in Ruby helps understand advanced divide-and-conquer techniques and the flexibility of recursive and iterative approaches. In this article, we will explore multiple ways to implement Ternary Search, making it easy for beginners to follow and apply.
Program 1: Recursive Ternary Search
This program demonstrates Ternary Search using a recursive approach to find a target value in a sorted array.
# Program 1: Recursive Ternary Search
def ternary_search_recursive(array, target, left = 0, right = nil)
right = array.length - 1 if right.nil?
return -1 if left > right
third1 = left + (right - left) / 3
third2 = right - (right - left) / 3
if array[third1] == target
return third1
elsif array[third2] == target
return third2
elsif target < array[third1]
ternary_search_recursive(array, target, left, third1 - 1)
elsif target > array[third2]
ternary_search_recursive(array, target, third2 + 1, right)
else
ternary_search_recursive(array, target, third1 + 1, third2 - 1)
end
end
numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 12
index = ternary_search_recursive(numbers, target)
if index != -1
puts "Element #{target} found at index #{index} (recursive)"
else
puts "Element #{target} not found (recursive)"
endIn this recursive approach, we calculate two midpoints that divide the array into three segments. The function then calls itself on the segment likely containing the target. Beginners can see how recursion naturally applies the divide-and-conquer principle to reduce search space efficiently.
Program 2: Iterative Ternary Search
Ternary Search can also be implemented iteratively, which avoids recursive calls and uses loops to narrow down the search.
# Program 2: Iterative Ternary Search
def ternary_search_iterative(array, target)
left = 0
right = array.length - 1
while left <= right
third1 = left + (right - left) / 3
third2 = right - (right - left) / 3
if array[third1] == target
return third1
elsif array[third2] == target
return third2
elsif target < array[third1]
right = third1 - 1
elsif target > array[third2]
left = third2 + 1
else
left = third1 + 1
right = third2 - 1
end
end
-1
end
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17]
target = 7
index = ternary_search_iterative(numbers, target)
if index != -1
puts "Element #{target} found at index #{index} (iterative)"
else
puts "Element #{target} not found (iterative)"
endIn the iterative version, we use a while loop to continuously reduce the search range by comparing with two midpoints. Beginners can understand how loops can replace recursion while keeping the same divide-and-conquer logic.
Program 3: Ternary Search for Floating-Point Numbers
Ternary Search works naturally with floating-point numbers as long as the array is sorted.
# Program 3: Ternary Search with floating-point numbers
def ternary_search_iterative(array, target)
left = 0
right = array.length - 1
while left <= right
third1 = left + (right - left) / 3
third2 = right - (right - left) / 3
if array[third1] == target
return third1
elsif array[third2] == target
return third2
elsif target < array[third1]
right = third1 - 1
elsif target > array[third2]
left = third2 + 1
else
left = third1 + 1
right = third2 - 1
end
end
-1
end
numbers = [0.5, 1.1, 2.4, 3.6, 4.8, 5.9]
target = 3.6
index = ternary_search_iterative(numbers, target)
if index != -1
puts "Floating-point element #{target} found at index #{index}"
else
puts "Floating-point element #{target} not found"
endThe algorithm’s comparisons and mid-point calculations apply equally to floats. Beginners can see the flexibility of Ternary Search across numeric types.
Program 4: Ternary Search on Large Datasets
This program demonstrates the efficiency of Ternary Search on a larger array, showing its practical application in sizable datasets.
# Program 4: Ternary Search on large dataset
def ternary_search_iterative(array, target)
left = 0
right = array.length - 1
while left <= right
third1 = left + (right - left) / 3
third2 = right - (right - left) / 3
if array[third1] == target
return third1
elsif array[third2] == target
return third2
elsif target < array[third1]
right = third1 - 1
elsif target > array[third2]
left = third2 + 1
else
left = third1 + 1
right = third2 - 1
end
end
-1
end
numbers = (1..1000).to_a
target = 678
index = ternary_search_iterative(numbers, target)
if index != -1
puts "Element #{target} found at index #{index} in large dataset"
else
puts "Element #{target} not found in large dataset"
endBy dividing the array into three segments each time, the algorithm quickly narrows down the range containing the target, making it efficient for large sorted arrays. Beginners can see the advantage of multi-way search over linear scanning.
Frequently Asked Questions (FAQ)
Ternary Search is a powerful algorithm, and beginners often have questions:
Q1: What is the time complexity of Ternary Search?
Ternary Search has a time complexity of O(log₃ n), slightly better in theory than Binary Search for certain cases, but in practice the difference is often negligible.
Q2: Can Ternary Search work on unsorted arrays?
No, the array must be sorted to ensure correct results.
Q3: Is recursive or iterative Ternary Search better?
Recursive is easier to understand conceptually, while iterative avoids stack overhead and is preferred for very large datasets.
Q4: Can Ternary Search handle floating-point numbers?
Yes, it works as long as the array is sorted and supports comparisons.
Q5: When is Ternary Search preferable over Binary Search?
Ternary Search can be slightly faster when function evaluation is expensive in optimization problems, but for simple searches, Binary Search is often sufficient.
Conclusion
In this article, we explored how to implement Ternary Search in Ruby using recursive and iterative approaches, including handling floating-point numbers and large datasets. Ternary Search builds on the divide-and-conquer principle, dividing the search space into three parts to efficiently locate a target in a sorted array. By practicing these examples, beginners can learn how to apply multi-way search strategies and understand the flexibility and efficiency of advanced search algorithms. Mastering Ternary Search equips programmers with another powerful tool for solving search and optimization problems efficiently.
