The triple search (Ternary search) is a method in computer science for searching for the maxima and minima of a function , which either increases first, then decreases , or vice versa. The ternary search determines that the minimum or maximum cannot lie in either the first or the last third of the area, and then repeats the search on the remaining two thirds. A triple search demonstrates a divide-and-conquer programming paradigm.
Function
Suppose that we are looking for the maximum of the function f ( x ), and that we know that the maximum lies between A and B. For the algorithm to be applicable, there must be some value of x , such that
- for all a , b , for which A ≤ a <b ≤ x , f (a) <f (b) holds, and
- for all a , b for which x ≤ a <b ≤ B , f (a)> f (b) holds.
Algorithm
/ **
Finds the maximum of a function with one extremum between l and r.
To find the minimum - it is enough to swap in the if / else branches.
* /
double l = ..., r = ..., EPS = ...; // input data
double m1 , m2 ;
while ( r - l > EPS ) {
m1 = l + ( r - l ) / 3 ;
m2 = r - ( r - l ) / 3 ;
if ( f ( m1 ) < f ( m2 ))
l = m1 ;
else
r = m2 ;
}
See also
- Binary search (used to find the point where the derivative changes the sign)
- Newton's method (used to find the point where the derivative vanishes)
- The golden section method (similar to the threefold search, useful if, for one iteration, the calculation of f takes the most time)
- Interpolating search
- Linear search