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.
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:
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 land r, i.e. we are actually using iterations asking desired relative error .