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 (see search algorithm).

The function

Assume we are looking for a maximum of f(x) 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

for all a,b with A ≤ a < b ≤ x, we have f(a) < f(b), and
for all a,b with x ≤ a < b ≤ B, we have f(a) > f(b).

Algorithm

Let $f (x)$ be a unimodal function on some interval [l; r]. Take any two points $m 1$ and $m 2$ in this segment: $l < m 1 < m 2 < r$ . Then there are three possibilities:

if $f (m 1) < f (m 2)$ , then the required maximum can not be located on the left side - $[l; m 1]$ . It means that the maximum further makes sense to look only in the interval $[m 1; r]$
if $f (m 1) > f (m 2)$ , that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side - $[m 2; r]$ , so go to the segment $[l; m 2]$
if $f (m 1) = f(m 2)$ , then the search should be conducted in $[m 1; m 2]$ , 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 $m 1$ and $m 2$ :

$m 1 = l + (r - l)/3$
$m 2 = r - (r - l)/3$

Run time order: $T(n)=T(2n/3)+1=\Theta (\log n)$

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

gollark: 3.

gollark: Ye's.

gollark: Repairing gives 1XP per cannon repaired, *but* costs 1 more snow.

gollark: Yes.

gollark: Also a bit ridiculous that they had to do that instead of just *having TJ09 fix the stupid things*.

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.