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).
[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)
