Ternary search explained

A ternary search algorithm^[1] is a technique in computer science for finding the minimum or maximum of a unimodal function.

The function

Assume we are looking for a maximum of

and that we know the maximum lies somewhere between and . For the algorithm to be applicable, there must be some value such that

• for all

with , we have , and

• for all

with , we have .

Algorithm

Let

be a unimodal function on some interval . Take any two points and in this segment: . Then there are three possibilities:

• if

, then the required maximum can not be located on the left side – . It means that the maximum further makes sense to look only in the interval

• if

, that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side – , so go to the segment

• if

, then the search should be conducted in , but this case can be attributed to any of the previous two (in order to simplify the code). Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.choice points and :

Run time order

Recursive algorithm

def ternary_search(f, left, right, absolute_precision) -> float: """Left and right are the current bounds; the maximum is between them. """ if abs(right - left) < absolute_precision: return (left + right) / 2

left_third = (2*left + right) / 3 right_third = (left + 2*right) / 3

if f(left_third) < f(right_third): return ternary_search(f, left_third, right, absolute_precision) else: return ternary_search(f, left, right_third, absolute_precision)

Iterative algorithm

def ternary_search(f, left, right, absolute_precision) -> float: """Find maximum of unimodal function f within [left, right]. To find the minimum, reverse the if/else statement or reverse the comparison. """ while abs(right - left) >= absolute_precision: left_third = left + (right - left) / 3 right_third = right - (right - left) / 3

if f(left_third) < f(right_third): left = left_third else: right = right_third

# Left and right are the current bounds; the maximum is between them return (left + right) / 2

See also

• Newton's method in optimization (can be used to search for where the derivative is zero)
• Golden-section search (similar to ternary search, useful if evaluating f takes most of the time per iteration)
• Binary search algorithm (can be used to search for where the derivative changes in sign)
• Interpolation search
• Exponential search
• Linear search

Notes and References

1. Web site: Ternary Search . cp-algorithms.com . 21 August 2023.