
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(1x) 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 differentiationbased 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.] 