Ternary search

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 and that we know the maximum lies somewhere between and . For the algorithm to be applicable, there must be some value such that

• for all with , we have , and
• for all with , we have .

Algorithm

Let be a unimodal function on some interval . Take any two points and in this segment: . Then there are three possibilities:

• if , then the required maximum can not be located on the left side – . It means that the maximum further makes sense to look only in the interval
• if , that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side – , so go to the segment
• if , then the search should be conducted in , 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 and :

Run time order

(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