Introduction

Ternary search is a search that finds a local minimum or maximum value in a function given an interval from A to B.

If there are multiple local minimum and maximum values, ternary search will only find one of them but it will not necessarily be the maximum or minimum.

Implementation

Suppose we have a function f(x) with only one max point between A and B. We want to find the point (M, f(M)) where f(M) is the maximum between A and B.

We split the range from A to B into three intervals. At every iteration of our algorithm, we can narrow down the range by 1/3 and we have a new interval. At every step, we can remove one of the intervals based on the following:

Let m1 by 1/3 of the way from A and B and let m2 be 2/3 of the way from B.

Case 1 : f(m1) < f(m2)

  • Case 1.1: m1 < m2 < M, so m1 < M

  • Case 1.2: m1 < M < m2, so m1 < M

  • Case 1.3: M < m1 < m2 is not possible.

Thus if f(m1) < f(m2), then m1 < M, so we only need to search from m1 to B.

Case 2: f(m1) >= f(m2)

  • Case 2.1: m1 < M < m2, so M < m2

  • Case 2.2: M < m1 < m2, so M < m2

  • Case 2.3: m1 < m2 < M is not possible

Thus, if f(m1) >= f(m2), then M < m2, so we only need to search from A to m2.

Therefore, based on the values of f(m1) and f(m2), we can always remove a third of the range. We can keep repeating this until the range is within a very small threshold such as 0.0001.

Example

Example of ternary search:

Suppose we have a function f(x) with a maximum point between A and B.

We find m1 (1/3) point and m2 (2/3) point between A and B.

Since f(m1) > f(m2), then we can reduce the range from A to m2. We find the new m1 and m2 points.

Since f(m1) < f(m2), then we can reduce the range from m1 to B. We find the new m1 and m2 points.

Since f(m1) < f(m2), then we can reduce the range from m1 to B. We find the new m1 and m2 points.

Since f(m1) < f(m2), then we can reduce the range from m1 to B. We find the new m1 and m2 points.

We keep repeating this until we narrow down the range to within a small threshold and we can find the point where f(x) is maximum.

Formalization

Let f(x) be the function.
Let (a, b) be interval of search.

Let tern(a,b) return M where f(M) is the maximum.

Let m1 = a + (b - a) / 3
Let m2 = a + (b - a) * 2 / 3

tern(a,b) = (a + b) / 2 if |f(a) - f(b)| < epsilon
tern(a,b) = tern(m1, b) if f(a) < f(b)
tern(a,b) = tern(a, m2) otherwise

Code

public double tern(double a,double b){
  if (Math.abs(f(a) - f(b)) < 0.0001) {
    return (a + b) / 2.0;
  }
  double m1 = a + (b - a) / 3.0;
  double m2 = a + (b - a) * 2.0 / 3.0;
  if (f(m1) < f(m2)) {
    return tern(m1, b);
  } else {
    return tern(a, m2);
  }
}