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).

Unimodality We are given a function $f(x)$ which is Unimodal Function on an interval $[l,r]$.

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

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

// Function to perform Ternary Search (iteratively)
int ternarySearch(int l, int r, int key, int ar[])
 
{
	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;
		}
 
		// Since key is not present at mid,
		// check in which region it is present
		// then repeat the Search operation
		// in that region
 
		if (key < ar[mid1]) {
 
			// The key lies in between l and mid1
			r = mid1 - 1;
		}
		else if (key > ar[mid2]) {
 
			// The key lies in between mid2 and r
			l = mid2 + 1;
		}
		else {
 
			// The key lies in between mid1 and mid2
			l = mid1 + 1;
			r = mid2 - 1;
		}
	}
	// Key not found
	return -1;
}
 
// Driver code
int main()
{
	int l, r, p, key;
 
	// Get the array
	// Sort the array if not sorted
	int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
	// Starting index
	l = 0;
 
	// length of array
	r = 9;
 
	// Checking for 5
 
	// Key to be searched in the array
	key = 5;
 
	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);
 
	// Print the result
	cout << "Index of "<<key<<" is " << p << endl;
 
	// Checking for 50
 
	// Key to be searched in the array
	key = 50;
 
	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);
 
	// Print the result
	cout << "Index of "<<key<<" is " << p;
}