March 24, 2025

Ternary Search¶

We are given a function $f (x)$ which is unimodal on an interval $[l, r]$ . By unimodal function, we mean one of two behaviors of the function:

The function strictly increases first, reaches a maximum (at a single point or over an interval), and then strictly decreases.
The function strictly decreases first, reaches a minimum, and then strictly increases.

In this article, we will assume the first scenario. The second scenario is completely symmetrical to the first.

The task is to find the maximum of function $f (x)$ on the interval $[l, r]$ .

Algorithm¶

Consider any 2 points $m_{1}$ , and $m_{2}$ in this interval: $l < m_{1} < m_{2} < r$ . We evaluate the function at $m_{1}$ and $m_{2}$ , i.e. find the values of $f (m_{1})$ and $f (m_{2})$ . Now, we get one of three options:

$f (m_{1}) < f (m_{2})$

The desired maximum can not be located on the left side of $m_{1}$ , i.e. on the interval $[l, m_{1}]$ , since either both points $m_{1}$ and $m_{2}$ or just $m_{1}$ belong to the area where the function increases. In either case, this means that we have to search for the maximum in the segment $[m_{1}, r]$ .
$f (m_{1}) > f (m_{2})$

This situation is symmetrical to the previous one: the maximum can not be located on the right side of $m_{2}$ , i.e. on the interval $[m_{2}, r]$ , and the search space is reduced to the segment $[l, m_{2}]$ .
$f (m_{1}) = f (m_{2})$

We can see that either both of these points belong to the area where the value of the function is maximized, or $m_{1}$ is in the area of increasing values and $m_{2}$ is in the area of descending values (here we used the strictness of function increasing/decreasing). Thus, the search space is reduced to $[m_{1}, m_{2}]$ . To simplify the code, this case can be combined with any of the previous cases.

Thus, based on the comparison of the values in the two inner points, we can replace the current interval $[l, r]$ with a new, shorter interval $[l^{'}, r^{'}]$ . Repeatedly applying the described procedure to the interval, we can get an arbitrarily short interval. Eventually, its length will be less than a certain pre-defined constant (accuracy), and the process can be stopped. This is a numerical method, so we can assume that after that the function reaches its maximum at all points of the last interval $[l, r]$ . Without loss of generality, we can take $f (l)$ as the return value.

We didn't impose any restrictions on the choice of points $m_{1}$ and $m_{2}$ . This choice will define the convergence rate and the accuracy of the implementation. The most common way is to choose the points so that they divide the interval $[l, r]$ into three equal parts. Thus, we have

m_{1} = l + \frac{(r - l)}{3}

m_{2} = r - \frac{(r - l)}{3}

If $m_{1}$ and $m_{2}$ are chosen to be closer to each other, the convergence rate will increase slightly.

Run time analysis¶

T (n) = T (2 n / 3) + O (1) = Θ (\log n)

It can be visualized as follows: every time after evaluating the function at points $m_{1}$ and $m_{2}$ , we are essentially ignoring about one third of the interval, either the left or right one. Thus the size of the search space is $2 n / 3$ of the original one.

Applying Master's Theorem, we get the desired complexity estimate.

The case of the integer arguments¶

If $f (x)$ takes integer parameter, the interval $[l, r]$ becomes discrete. Since we did not impose any restrictions on the choice of points $m_{1}$ and $m_{2}$ , the correctness of the algorithm is not affected. $m_{1}$ and $m_{2}$ can still be chosen to divide $[l, r]$ into 3 approximately equal parts.

The difference occurs in the stopping criterion of the algorithm. Ternary search will have to stop when $(r - l) < 3$ , because in that case we can no longer select $m_{1}$ and $m_{2}$ to be different from each other as well as from $l$ and $r$ , and this can cause an infinite loop. Once $(r - l) < 3$ , the remaining pool of candidate points $(l, l + 1, \dots, r)$ needs to be checked to find the point which produces the maximum value $f (x)$ .

Golden section search¶

In some cases computing $f (x)$ may be quite slow, but reducing the number of iterations is infeasible due to precision issues. Fortunately, it is possible to compute $f (x)$ only once at each iteration (except the first one).

To see how to do this, let's revisit the selection method for $m_{1}$ and $m_{2}$ . Suppose that we select $m_{1}$ and $m_{2}$ on $[l, r]$ in such a way that $\frac{r - l}{r - m_{1}} = \frac{r - l}{m_{2} - l} = φ$ where $φ$ is some constant. In order to reduce the amount of computations, we want to select such $φ$ that on the next iteration one of the new evaluation points $m_{1}^{'}$ , $m_{2}^{'}$ will coincide with either $m_{1}$ or $m_{2}$ , so that we can reuse the already computed function value.

Now suppose that after the current iteration we set $l = m_{1}$ . Then the point $m_{1}^{'}$ will satisfy $\frac{r - m_{1}}{r - m_{1}^{'}} = φ$ . We want this point to coincide with $m_{2}$ , meaning that $\frac{r - m_{1}}{r - m_{2}} = φ$ .

Multiplying both sides of $\frac{r - m_{1}}{r - m_{2}} = φ$ by $\frac{r - m_{2}}{r - l}$ we obtain $\frac{r - m_{1}}{r - l} = φ \frac{r - m_{2}}{r - l}$ . Note that $\frac{r - m_{1}}{r - l} = \frac{1}{φ}$ and $\frac{r - m_{2}}{r - l} = \frac{r - l + l - m_{2}}{r - l} = 1 - \frac{1}{φ}$ . Substituting that and multiplying by $φ$ , we obtain the following equation:

$φ^{2} - φ - 1 = 0$

This is a well-known golden section equation. Solving it yields $\frac{1 \pm \sqrt{5}}{2}$ . Since $φ$ must be positive, we obtain $φ = \frac{1 + \sqrt{5}}{2}$ . By applying the same logic to the case when we set $r = m_{2}$ and want $m_{2}^{'}$ to coincide with $m_{1}$ , we obtain the same value of $φ$ as well. So, if we choose $m_{1} = l + \frac{r - l}{1 + φ}$ and $m_{2} = r - \frac{r - l}{1 + φ}$ , on each iteration we can re-use one of the values $f (x)$ computed on the previous iteration.

Implementation¶

double ternary_search(double l, double r) {
    double eps = 1e-9;              //set the error limit here
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //evaluates the function at m1
        double f2 = f(m2);      //evaluates the function at m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //return the maximum of f(x) in [l, r]
}

Here eps is in fact the absolute error (not taking into account errors due to the inaccurate calculation of the function).

Instead of the criterion r - l > eps, we can select a constant number of iterations as a stopping criterion. The number of iterations should be chosen to ensure the required accuracy. Typically, in most programming challenges the error limit is $10^{- 6}$ and thus 200 - 300 iterations are sufficient. Also, the number of iterations doesn't depend on the values of $l$ and $r$ , so the number of iterations corresponds to the required relative error.

Practice Problems¶

Contributors:

likecs (39.32%)
SYury (17.09%)
tcNickolas (16.24%)
AbhijeetKrishnan (11.11%)
adamant-pwn (5.9799999999999995%)
Morass (5.13%)
joaquingx (1.71%)
Ahmed-Elshitehi (0.85%)
jxu (0.85%)
lovish24-ctrl (0.85%)
p1unit (0.85%)