JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Ternary Search | Reply
Problem:

You have a function f in an interval [a,b] of real numbers, and you want to find the x for which f(x) is maximized. You know that the function f is unimodal: it is strictly increasing in the interval [a,x], and strictly decreasing in the interval [x,b].

Solution:

If we are working with an interval of integers, not an interval of reals, simply use binary search (see "binary search" recipe). (The property P(x) we are working with is the following one: f(x) > f(x+1).)

For reals, use the following algorithm, known as ternary search:
double l = a, r = b;
 
for(int i=0; i<200; i++) {
  double l1 = (l*2+r)/3;
  double l2 = (l+2*r)/3;
  if(f(l1) > f(l2)) r = l2; else l = l1;
  }
 
x = l;

Discussion:

This works because after each step the interval [a,b] is reduced to 2/3 of its previous size. After 200 steps, we will know the answer up to an error of at most (2/3)^200 of the original interval, which should be precise enough for TopCoder.

Don't forget that ternary search is not the only way of finding the maximum of a function; some basic knowledge of differentiation might also be helpful. In case if f is easily differentiable, you need to find x such that f'(x)=0; for some functions f such x can be calculated easily, without having to go through 200 iterations. For example, we can easily check that the function f(x) = x(1-x) reaches its maximum at 1/2. However, you need to be careful about floating point errors and situations where the maximum is reached at the end of the interval; ternary search is less prone to such errors, and is quick to implement once you understand it well.

Another option would be to use binary search: find smallest x such that f'(x)<=0. This correctly returns one of the ends of the interval if x is actually one of them. There is probably usually not much point in doing that, but it attains the same precision as ternary search in roughly 1.7 times less iterations (and it makes only one call to f' per iteration).

Another common problem is to maximize some function f(x,y) of two variables over a rectangular area. This can be done by doing two nested ternary searches: for each x, maximize f(x,y) using ternary search, let this be g(x); now, maximize g(x). You need to make sure that g(x) and f(x,y) for fixed x are unimodal. Of course, a similar method also works
for more than 2 dimensions.

Don't forget about the unimodality requirement! Without it, you need to use a different technique. (Simple differentiation-based techniques also fail in this case.)

[I think this should work in all three major languages, except that maybe the type name should be changed. This is partial work for now, I need someone to suggest good recent problems where these techniques used. Nickolas's outline suggested a single recipe for both binary and ternary search, but I think that although the implementation is similar, these two are used for different problems, so it is better to have two recipes.]
Re: Ternary Search (response to post by Eryx) | Reply
The same as the binary search: I prefer to use a fixed number of iterations (say 200), because that is guaranteed to terminate.

BTW I agree that binary and ternary searches are used for different problems so it makes sense to keep them in separate recipes.
Re: Ternary Search (response to post by dimkadimon) | Reply
Nice tutorial:)
Can someone suggest problems to practice ternary search?
Re: Ternary Search (response to post by Eryx) | Reply
> This works because after each step the interval [a,b] is reduced to 2/3 of its previous size

and unimodality guarantees that the 1/3 (outside the new interval) that is removed cannot contain the maximum.
Re: Ternary Search (response to post by Eryx) | Reply
> in roughly 1.7 times less iterations (and it makes only one call to f' per iteration)

So this version of ternary search is effectively 3.4 times slower than binary search, assuming same speed of calculation f(x) and f'(x).

There is though a version of ternary search that's only 1.44 times slower than binary search and doesn't need to have f'(x) at all.
All you need is divide the range at golden ratio points. The next iteration range will be 1.6 times smaller, and as a benefit you can reuse one of the previously calculated f(x) values in the new iteration, so only one call of f(x) per iteration is needed.
RSS