Ternary search

Short description: Algorithm for finding the extrema of a unimodal function

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 [math]\displaystyle{ f(x) }[/math] and that we know the maximum lies somewhere between [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]. For the algorithm to be applicable, there must be some value [math]\displaystyle{ x }[/math] such that

• for all [math]\displaystyle{ a, b }[/math] with [math]\displaystyle{ A \leq a \lt b \leq x }[/math], we have [math]\displaystyle{ f(a) \lt f(b) }[/math], and
• for all [math]\displaystyle{ a, b }[/math] with [math]\displaystyle{ x \leq a \lt b \leq B }[/math], we have [math]\displaystyle{ f(a) \gt f(b) }[/math].

Algorithm

Let [math]\displaystyle{ f(x) }[/math] be a unimodal function on some interval [math]\displaystyle{ [l; r] }[/math]. Take any two points [math]\displaystyle{ m_1 }[/math] and [math]\displaystyle{ m_2 }[/math] in this segment: [math]\displaystyle{ l \lt m_1 \lt m_2 \lt r }[/math]. Then there are three possibilities:

• if [math]\displaystyle{ f(m_1) \lt f(m_2) }[/math], then the required maximum can not be located on the left side – [math]\displaystyle{ [l; m_1] }[/math]. It means that the maximum further makes sense to look only in the interval [math]\displaystyle{ [m_1; r] }[/math]
• if [math]\displaystyle{ f(m_1) \gt f(m_2) }[/math], that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side – [math]\displaystyle{ [m_2; r] }[/math], so go to the segment [math]\displaystyle{ [l; m_2] }[/math]
• if [math]\displaystyle{ f(m_1) = f(m_2) }[/math], then the search should be conducted in [math]\displaystyle{ [m_1; m_2] }[/math], 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 [math]\displaystyle{ m_1 }[/math] and [math]\displaystyle{ m_2 }[/math]:

• [math]\displaystyle{ m_1 = l + (r - l) / 3 }[/math]
• [math]\displaystyle{ m_2 = r - (r - l) / 3 }[/math]

Run time order

[math]\displaystyle{ T(n) = T(2n/3) + 1 = \Theta(\log n) }[/math]

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
• N Dimensional Ternary Search Implementation