Ternary search

From Wikipedia, the free encyclopedia

A ternary search algorithm is a computer science technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa. A ternary search determines that the minimum or maximum cannot be in either the first third or last third of the domain and then repeats on the remaining two-thirds. A ternary search is an example of a divide and conquer algorithm (see search algorithm).

1 The function
2 The algorithm
3 See also
4 References

[edit] The function

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 A ≤ a < b ≤ x, we have f(a) < f(b), and
for all a,b with x ≤ a < b ≤ B, we have f(a) > f(b).

[edit] The algorithm

function ternarySearch(f, left, right, absolutePrecision) 
//left and right are the current bounds; the maximum is between them
    if (right-left < absolutePrecision) return (left+right)/2
    leftThird := (left*2+right)/3
    rightThird := (left+right*2)/3
    if (f(leftThird) < f(rightThird))
        return ternarySearch(f, leftThird, right, absolutePrecision)
    else
        return ternarySearch(f, left, rightThird, absolutePrecision)
end

[edit] See also

Binary search (can be used to search for where the derivative changes in sign)
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)
Interpolation search
Linear search

[edit] References

This article does not cite any references or sources. (May 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.