Loading...
Divide and conquer by three. Ternary search divides the search space into three parts using two midpoints, identifying which segment the target (or extremum) resides in.
O(log₃ n)
Logarithmic time
O(1)
Iterative version
Lower Utility
Binary Search is usually faster
Unimodal Funcs
Finding min/max points
Like Binary Search, Ternary Search is a Divide and Conquer algorithm. However, instead of splitting the range into two halves, it splits it into three equal parts using two midpoints:
left + (right - left) / 3right - (right - left) / 3While ternary search has a smaller number of iterations than binary search ($ \log_3 n $ iterations vs $ \log_2 n $ iterations), it performs two comparisons per iteration instead of one. In most environments, the extra comparison makes it slower in practice than binary search.
Initialize L=0 and R=n-1.
Verify if the range L..R is valid.
Pick two midpoints splitting the range into thirds.
Decision Logic
Target matches m1 or m2? Exit.
Target smaller than m1? Look in left third.
Target larger than m2? Look in right third.
Otherwise? Look in middle third.
def ternary_search(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
# Divide range into three parts
third = (r - l) // 3
m1 = l + third
m2 = r - third
# Check midpoints
if arr[m1] == target: return m1
if arr[m2] == target: return m2
# Determine next sub-range
if target < arr[m1]:
r = m1 - 1
elif target > arr[m2]:
l = m2 + 1
else:
l = m1 + 1
r = m2 - 1
return -1
# Time Complexity: O(log3 n) -> O(log n)
# Space Complexity: O(1)A unimodal function is a function which strictly increases and then strictly decreases (or vice-versa). Ternary search is the go-to algorithm for finding the maximum or minimum point of such functions in continuous space.
Predicting peak projectile height or resonance points.
Finding optimal pricing or resource allocation peaks.