Ternary search
A ternary search algorithm[1] 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
References
![]() | Original source: https://en.wikipedia.org/wiki/Ternary search.
Read more |