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 f ( x ) {\displaystyle f(x)} and that we know the maximum lies somewhere between A {\displaystyle A} and B {\displaystyle B} . For the algorithm to be applicable, there must be some value x {\displaystyle x} such that
for all a , b {\displaystyle a,b} with A ≤ a < b ≤ x {\displaystyle A\leq a<b\leq x} , we have f ( a ) < f ( b ) {\displaystyle f(a)<f(b)} , and for all a , b {\displaystyle a,b} with x ≤ a < b ≤ B {\displaystyle x\leq a<b\leq B} , we have f ( a ) > f ( b ) {\displaystyle f(a)>f(b)} .
Algorithm Let f ( x ) {\displaystyle f(x)} be a unimodal function on some interval [ l ; r ] {\displaystyle [l;r]} . Take any two points m 1 {\displaystyle m_{1}} and m 2 {\displaystyle m_{2}} in this segment: l < m 1 < m 2 < r {\displaystyle l<m_{1}<m_{2}<r} . Then there are three possibilities:
if f ( m 1 ) < f ( m 2 ) {\displaystyle f(m_{1})<f(m_{2})} , then the required maximum can not be located on the left side – [ l ; m 1 ] {\displaystyle [l;m_{1}]} . It means that the maximum further makes sense to look only in the interval [ m 1 ; r ] {\displaystyle [m_{1};r]}
if f ( m 1 ) > f ( m 2 ) {\displaystyle 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 ] {\displaystyle [m_{2};r]} , so go to the segment [ l ; m 2 ] {\displaystyle [l;m_{2}]}
if f ( m 1 ) = f ( m 2 ) {\displaystyle f(m_{1})=f(m_{2})} , then the search should be conducted in [ m 1 ; m 2 ] {\displaystyle [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 {\displaystyle m_{1}} and m 2 {\displaystyle m_{2}} :
m 1 = l + ( r − l ) / 3 {\displaystyle m_{1}=l+(r-l)/3}
m 2 = r − ( r − l ) / 3 {\displaystyle m_{2}=r-(r-l)/3}
Run time order
T ( n ) = T ( 2 n / 3 ) + O ( 1 ) = Θ ( log n ) {\displaystyle T(n)=T(2n/3)+O(1)=\Theta (\log n)} (by the Master Theorem)
Recursive algorithm
Iterative algorithm
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
References
