We will use Ternary search for this problem

Supposing the given a function f (x), is unimodal on some interval [l , r]. By unimodal is meant one of two options.

1. Strictly increasing function first, then reaches a maximum (at one point or the whole segment), then strictly decreasing.
2. Symmetrical: the function decreases first decreases, reaches a minimum, increases.

Here, we will consider the first option, and the second will be symmetrical to the first option

Algorithm

Take any two points m1, and m2 in this segment: l < m1 < m2 < r. Calculate the values ​​of the function f (m1) and f (m2).

Then we get three options:

• If you find that f (m1) < f (m2) , the desired maximum can not be in the left-hand side, i.e, in part [ l , m1]. This is easily seen that if the left point of the function is smaller than the right, then either of these two points are in the area of "lifting" function, or only the left point is there. In any case, this means that the peak is meaningful to search on only the segment [m1 , r].
• If, on the contrary, f (m1 ) > f (m2) , then the situation is similar to the previous, up to symmetry. Now the desired maximum can not be on the right side, i.e. in part [m2 , r] , why go to the segment [l , m2].
• If f (m1) = f (m2), then either both of these points are in the region of the maximum, or the left point is in the ascending and the right in descending order (here essentially used that increase / decrease strict). Thus, after the search is meaningful in the segment [m1 , m2], but (in order to simplify the code), this case can be attributed to any of the previous two.

Thus, according to the comparison result of the function in two interior points instead of the current segment, we find [l; r]there is a new segment [l' , r']. We now repeat all the steps for this new segment, we again obtain a new, strictly smaller segment, etc.

Sooner or later the length of the segment will be a little lower than the predefined constants, accuracy, and the process can be stopped. This method is numerical, so after stopping the algorithm can approximately assume that all points of the interval [l , r]reaches its maximum.

It remains to note that we do not impose any restrictions on the choice of points m1 and m2. From this process, clearly, will depend on the rate of convergence (and error occurs). The most common way - choose a point so that the segment [l , r]was divided them into 3 equal parts:

However, a different choice of when m1 and m2 closer to each other, the convergence rate of increase slightly.

Case of the integer argument

If the argument to f , an integer, the segment [l , r]also becomes discrete, however, because we do not impose any restrictions on the choice of points m1 and m2 ,then on the correctness of the algorithm is not affected. We can still choose m1 and m2 so that they divide the segment [l , r] into 3 parts, but only approximately equal.

Wherein the second point - the stopping criterion of the algorithm. In this case, ternary search will have to stop when it will be r - l <3, because in this case is no longer possible to select a point m1 and m2 so varied and different from l, and r, and this can lead to infinite loops. After ternary search algorithm will stop and r - l <3, of the remaining number of candidate points (l , l + 1, ............ , r) is necessary to select a point with the maximum value of the function.

Implementation:

double l = ..., r = ..., EPS = ...; 
while (r - l > EPS) {
   double m1 = l + (r - l) / 3,
      m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

Here, EPS- in fact, the absolute error response (not counting errors due to inaccurate calculation of the function).

Instead of the criterion while (r - l> EPS) can be selected and a stopping criterion:

for (int it=0; it<iterations; ++it)

On the one hand, it is necessary to choose a constant iterations to ensure the required accuracy (typically just a few hundred, to achieve maximum accuracy). But, on the other hand, the number of iterations stops depend on the absolute values l​​and r, i.e. we are actually using iterations asking desired relative error .