Ternary search

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 either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two-thirds. A ternary search is an example of a divide and conquer algorithm (see search algorithm).

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

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

ee 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

References