ternary search

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 , we have , and
• for all $a,\; b$ with , we have $f(a)\; >\; f(b)$.

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

• if , 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)\; +\; O(1)$

= \Theta(\log n) (by the Master Theorem)

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)

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

• 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

{{Reflist}}

Category:Articles with example Python (programming language) code

Category:Search algorithms

Category:Optimization algorithms and methods