## 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 m_{1} by 1/3 of the way from A and B and let m_{2} be 2/3 of the way from B.

**Case 1** : f(m_{1}) < f(m_{2})

**Case 1.1**: m_{1}< m_{2}< M, so m_{1}< M**Case 1.2**: m_{1}< M < m_{2}, so m_{1}< M**Case 1.3**: M < m_{1}< m_{2}is not possible.

Thus if f(m_{1}) < f(m_{2}), then m_{1} < M, so we only need to search from m_{1} to B.

**Case 2**: f(m_{1}) >= f(m_{2})

**Case 2.1**: m_{1}< M < m_{2}, so M < m_{2}**Case 2.2**: M < m_{1}< m_{2}, so M < m_{2}**Case 2.3**: m_{1}< m_{2}< M is not possible

Thus, if f(m_{1}) >= f(m_{2}), then M < m_{2}, so we only need to search from A to m_{2}.

Therefore, based on the values of f(m_{1}) and f(m_{2}), 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 m_{1} (1/3) point and m_{2} (2/3) point between A and B.

Since f(m_{1}) > f(m_{2}), then we can reduce the range from A to m_{2}. We find the new m_{1} and m_{2} points.

Since f(m_{1}) < f(m_{2}), then we can reduce the range from m_{1} to B. We find the new m_{1} and m_{2} points.

Since f(m_{1}) < f(m_{2}), then we can reduce the range from m_{1} to B. We find the new m_{1} and m_{2} points.

Since f(m_{1}) < f(m_{2}), then we can reduce the range from m_{1} to B. We find the new m_{1} and m_{2} 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); } }