Ternary search
Appearance
This article relies largely or entirely on a single source. (May 2007) |
A ternary search algorithm[1] is a technique in computer science for finding the minimum or maximum of a unimodal function.
The function
[edit]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
[edit]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
- (by the Master Theorem)
Recursive algorithm
[edit]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
[edit]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
[edit]- 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
References
[edit]- ^ "Ternary Search". cp-algorithms.com. Retrieved 21 August 2023.