Ternary Search

Given a unimodal function, the Ternary Search algorithm can be used to find the maximum or minimum value of a function.

What is a Unimodal function?

It is a function that is monotonically increasing for some x ≤ a and monotonically decreasing for some x ≥ b. The function has a maximum value of during the interval a ≤ x ≤ b. The maximum value can be at a single point(a == b) or a range(a ≤ x ≤ b). The definition can be extended to a function with a minimum value as well.

The algorithm works by selecting 2 points that divide the whole input into 3 parts. Let’s call those two points m1 and m2.

1. Region1: x < m1
2. Region2: m1 ≤ x ≤ m2
3. Region3: x > m2

There are three cases to consider:

1. Case 1: f(m1) < f(m2), during this case the maximum cannot lie in Region1. Therefore we can limit our search area to Region2 and Region3.
2. Case 2: f(m1) > f(m2), during this case the maximum cannot lie in Region3. Therefore we can limit our search area to Region1 and Region2.
3. Case 3: f(m1) == f(m2), during this case maximum lies in the Region2 only. As stated in our definition the function is monotonically increasing or decreasing except for the maximum value.

Algorithm:

// f(x) is the function to be maximized.
double ternarySearch(final double l, final double r){
    double lx = l, rx = r;
    double PRECISION = 1e6;
    while(rx - lx >= PRECISION){
      double m1 = (lx + lx + rx) / 3.0D;
      double m2 = (lx + rx + rx) / 3.0D; 
      
      if(f(m1) <= f(m2)){
        lx = m1;
      } else {
        rx= m2;
      }
    }
    
    return f(lx);
  }

In the above code snippet, instead of having a separate Case 3 we simplified the algorithm and merged Case 3 with Case 1. The while loop controls the precision of the value required. Instead of having a while loop conditional on PRECISION, we can run it for ~200 iterations for precision of 1e6.

Time Complexity

During each iteration of the algorithm, we are reducing our search space by 2/3 which essentially yields a runtime complexity of O(lg n).

Practice Questions:

1. https://leetcode.com/problems/best-position-for-a-service-centre/ [Solution]