Ternary search


A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function. A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two thirds. A ternary search is an example of a divide and conquer algorithm.

The function

Assume we are looking for a maximum of f and that we know the maximum lies somewhere between A and B. For the algorithm to be applicable, there must be some value x such that
Let be a unimodal function on some interval . Take any two points and in this segment:. Then there are three possibilities:
choice points and :
; 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