Difference between revisions of "Ternary search"

Revision as of 09:14, 1 January 2012

Ternary search is an algorithm similar to binary search. It is used when we have a function that is bitonic on a given interval instead of monotone, and we wish to optimize its value on that interval. That is, either the function first increases and then decreases, and we wish to find its maximum (that is, where it changes from increasing to decreasing), or it first decreases and then increases, and we wish to find the minimum. (In the former case, finding the minimum is trivial; it is at either the left edge or the right edge of the interval. In the latter case, finding the maximum is trivial.)

For the algorithm to work, we need the increase and decrease to be strict. Otherwise, we could have a pathological case in which the function is constant at all but one point, and then it would be impossible to find that point in the continuous case (and would be impossible to do it efficiently in the discrete case).

Should we wish to find a specific value, we can use binary search on the increasing part and the decreasing part separately, after having located the extremum and hence determined where the increasing part and decreasing part begin and end.

The function in question is usually defined on a continuous domain rather than a discrete domain, which gives the following pseudocode for the increasing-then-decreasing case:

// a: left edge of interval
// b: right edge of interval
// f: function
// epsilon: tolerance
input a, b, f, epsilon
l ← a
r ← b
while (r-l > epsilon)
    m1 ← (2*l + r)/3
    m2 ← (l + 2*r)/3
    if f(m1) < f(m2)
        l ← m1
    else
        r ← m2
print r

The reasoning is as follows. We split the interval into three equal subintervals: , , and . Then we evaluate at the intermediate points and . We then consider the result of the comparison:

• If , then the maximum can't possibly occur in the first interval, since then the function would be increasing from to the maximum, then decreasing from the maximum to , and then at some point increasing again since . So we discard the first interval.
• If , then the maximum can't possibly occur in the third interval, by similar reasoning.
• If , then the maximum has to be in the second interval; if it were in the first interval then the function would not be strictly decreasing afterward, and if it were in the third interval then the function would not be strictly increasing at the beginning.

Here, we can either discard the first or the third interval; it doesn't matter which. That's why we don't need a case in the code for this case. Intuitively, evaluating the function at the two intermediate points tips us off as to which "direction" to look in, as though we are climbing a hill. When the function is higher at the first than at the second, we know the maximum lies in one of the two left subintervals, and when it is higher at the second than at the first, we know the maximum lies in one of the two right subintervals. If the bitonicity is not strict, then we might not be able to obtain any useful information from the comparison, so this is not allowed.

The loop runs about times, since each iteration reduces the length of the interval by a factor of . Each iteration involves two evaluations of the function, so the total number of evaluations is about . This is , so the smaller the epsilon, the longer the search takes, but overall the time is logarithmic in the length of the initial interval.