CareerCup

Interesting problem.

A simple approach is to just increment in small steps from x1 to x2. This is O(|x2-x1|) and potentially inefficent.

There is a more efficient binary-search like algorithm. The idea is to narrow down the interval in which the minimum lies.

Given current interval (x,y), compute two new points ((2x + y)/3, (x+2y)/3), call it (a,b).

if a and b are "equal" you return a.

Compute convex(a) and convex(b).

If convex(a) < convex(b), then b is surely in the increasing arm of the function.

Thus you can pick (x,b) as the new search interval.

if convex(a) > convex(b), then a is surely in the decreasing arm of the function. You can pick (a,y) as the new search interval.

if convex(a) == convex(b), we can pick either (x,b) or (a,y).


Thus we have an O(log (|x2 -x1|) time algorithm, as we cut a fixed fraction of the interval each time.

Here is sample python (neither exemplary, nor properly tested)

def minima(x,y, f):
	err = 0.00000000000000000001
	a,b = (2.0*x + y)/3.0, (x+2.0*y)/3.0

	if b-a < err:
		return a

	delta = f(a) - f(b)

	if delta*delta < err*err:
		return minima(x,b,f)

	if delta < 0:
		return minima(x,b,f)

	if delta > 0:
		return minima(a,y,f)

	return b

def square(x):
	return x*x;

minima(-1.0,1.0, square)

Start with three intervals and determine whether they go net down or net up. If they're DDU or DDD (i.e the middle interval is net down), then you know the min is the 2nd or 3rd interval, so toss the first interval and split the third one. If they're DUU or UUU (i.e. the middle interval is net up), then you know the min is in the 1st or 2nd interval, so toss the third interval and split the first one. Keep applying the algorithm until your three intervals are suitably small.

Here is the algorithm :

minima( x1, x2)
mid = (x1+x2)/2;M = convex(mid);
lmid = (x1+mid)/2;L = convex(lmid);
rmid = (mid+x2)/2; R = convex(rmid);
If M < R && L
   then x1 = lmid;x2 = rmid;
else if M < L && M > R
   then x1 = lmid;
else if M < R && M > L
   then x2 = rmid;
go to line number 2;
if (x2-x1) < 1E-10
   output (x1+x2)/2;
   break;

If function is non decreasing or non increasing then we also use <=.
Complexity : Depends upon accuracy.

This is a straight forward ternary search problem
   double minima(int x1, int x2)
   {
              double lo(x1), hi(x2), x, y;
              while (fabs(x1-x2) >= 1e-6)
              {
                          x = (2*lo + hi)/3;
                          y = (2*hi + lo)/3;
                          if (x>= y) lo = x;
                          else hi = y;
              }
              return (lo+hi)/2;
   }