Ternary Search

I haven’t yet encountered a problem where this is needed. It is very similar to Binary Search, except that it reduces the time complexity even more, (log base 3).

• Today, first problem https://codeforces.com/problemset/problem/1999/G2 that requires this

Resources

• https://cp-algorithms.com/num_methods/ternary_search.html
• https://www.geeksforgeeks.org/ternary-search/

Version 1

This implements ternary search given an array ar.

int ternarySearch(int l, int r, int key) {
	while (r >= l) {
		// Find the mid1 and mid2
		int mid1 = l + (r - l) / 3;
		int mid2 = r - (r - l) / 3;
 
		// Check if key is present at any mid
		if (ar[mid1] == key) {
			return mid1;
		}
		if (ar[mid2] == key) {
			return mid2;
		}
 
		if (key < ar[mid1]) { // Somewhere in [l, mid1)
			r = mid1 - 1;
		}
		else if (key > ar[mid2]) { // Somewhere in (mid2, r]
			l = mid2 + 1;
		}
		else { // Somewhere in (mid1, mid2)
			l = mid1 + 1;
			r = mid2 - 1;
		}
	}
	// Key not found
	return -1;
}
 

Version 2

Used to solve for Unimodal Function.

We are given a function $f(x)$ which is Unimodal Function on an interval $[l,r]$. The task is to find the maximum of function $f(x)$ on the interval $[l,r]$.

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]
}

• Taken from https://cp-algorithms.com/num_methods/ternary_search.html
• Is this correct? Seems to only removes 1/3 of option? (i.e. 2/3 time)
  • It gets updated either to $[l,m_2]$ or $[m_1,r]$ , which are both 2/3 of option
• In this case, the nature of the problem forces us to end up doing a binary decision. We can’t be sure that it’s in the smaller interval $[l,m_1]$ (just come up with a counterexample)

So that seems slower than binary search??

• Note that the example above is a Continuous Function. If it was discrete, we can do binary search using the tricks that erichto taught you for Binary Search