Ternary search
A ternary search algorithm 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. Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.
; Run time order
Recursive algorithm
def ternary_search -> float:
"""Left and right are the current bounds;
the maximum is between them.
"""
if abs < absolute_precision:
return / 2
left_third = / 3
right_third = / 3
if f < f:
return ternary_search
else:
return ternary_search
Iterative algorithm
def ternary_search -> float:
"""Find maximum of unimodal function f within .
To find the minimum, reverse the if/else statement or reverse the comparison.
"""
while abs >= absolute_precision:
left_third = left + / 3
right_third = right - / 3
if f < f:
left = left_third
else:
right = right_third
# Left and right are the current bounds; the maximum is between them
return / 2