Idea behind Ternary Search

The idea behind Ternary Search is same as Binary Search but instead of dividing the search space into 2 parts and we divide it into 3 parts and remove one of them from the search space. Lets explore further with the help of an example:

Lets consider a Unimodal function f(x), such that we need to find the value of x, for which f(x) is minimum.

Here, we take 2 mid points (lets say, mid1 and mid2) between the range [l, r] divide the Search space into three parts.
Then calculate the value of the Unimodal function at mid1 and mid2.
According to the values of the Unimodal function at mid1 and mid2, we can have one of the following 3 cases,

Case1: f(mid1) < f(mid2), then reduce the search space to [l, mid2]

Case 2: f(mid1) > f(mid2), then reduce the search space to [mid1, r]

Case 3: f(mid1) = f(mid2), then reduce the search space to [mid1, mid2]

We keep on reducing the search space till we get our answer.

Similarly, we can apply ternary search to all the Unimodal Functions.

Implementation of Ternary Search:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Find the value of x in range [l, r] 
// for which f(x) is minimum
// f(x) = 2*(x^2) - 10*x + 2
 
double f(double x) {
    return 2 * (x * x) - 10 * x + 2;
}
 
 
int main() {
    double l = -1e5, r = 1e5;
    // Commonly the error limit is given as
    // 1e-6 or 1e-9
    while((r - l) >= 1e-9) {
        double mid1 = l + (r - l)/3.0;
        double mid2 = r - (r - l)/3.0;
        double f_mid1 = f(mid1);
        double f_mid2 = f(mid2);
        if (f_mid1 < f_mid2) {
            r = mid2;
        }
        else if(f_mid1 > f_mid2) {
            l = mid1;
        }
        else if(f_mid1 == f_mid2) {
            l = mid1;
            r = mid2;
        }
    }
    cout << setprecision(9) << l <<"\n";
     
    return 0;
}

Java

// Java code
 
public class MinimumValue {
    // Find the value of x in range [l, r] 
    // for which f(x) is minimum
    // f(x) = 2*(x^2) - 10*x + 2
 
    public static double f(double x) {
        return 2 * x * x - 10 * x + 2;
    }
 
    public static void main(String[] args) {
        double l = -1e5;
        double r = 1e5;
        double errorLimit = 1e-9;
 
        while ((r - l) >= errorLimit) {
            double mid1 = l + (r - l) / 3.0;
            double mid2 = r - (r - l) / 3.0;
            double f_mid1 = f(mid1);
            double f_mid2 = f(mid2);
 
            if (f_mid1 < f_mid2) {
                r = mid2;
            } else if (f_mid1 > f_mid2) {
                l = mid1;
            } else if (f_mid1 == f_mid2) {
                l = mid1;
                r = mid2;
            }
        }
 
        System.out.printf("%.1f\n", l);
    }
}
 
// This code is contributed by guptapratik

Python3

# Python Code
 
# Find the value of x in the range [l, r]
# for which f(x) is minimum
# f(x) = 2*(x^2) - 10*x + 2
 
def f(x):
    return 2 * x * x - 10 * x + 2
 
l = -1e5
r = 1e5
error_limit = 1e-9
 
while r - l >= error_limit:
    mid1 = l + (r - l) / 3.0
    mid2 = r - (r - l) / 3.0
    f_mid1 = f(mid1)
    f_mid2 = f(mid2)
 
    if f_mid1 < f_mid2:
        r = mid2
    elif f_mid1 > f_mid2:
        l = mid1
    else:
        l = mid1
        r = mid2
 
print(f'{l:.1f}')
 
# This code is contributed by guptapratik

C#

// C# Code
using System;
 
class MinimumValue
{
    // Find the value of x in the range [l, r]
    // for which f(x) is minimum
    // f(x) = 2*(x^2) - 10*x + 2
 
    static double f(double x)
    {
        return 2 * x * x - 10 * x + 2;
    }
 
    static void Main()
    {
        double l = -1e5;
        double r = 1e5;
        double errorLimit = 1e-9;
 
        while ((r - l) >= errorLimit)
        {
            double mid1 = l + (r - l) / 3.0;
            double mid2 = r - (r - l) / 3.0;
            double f_mid1 = f(mid1);
            double f_mid2 = f(mid2);
 
            if (f_mid1 < f_mid2)
            {
                r = mid2;
            }
            else if (f_mid1 > f_mid2)
            {
                l = mid1;
            }
            else if (f_mid1 == f_mid2)
            {
                l = mid1;
                r = mid2;
            }
        }
 
        Console.WriteLine($"{l:f1}"); // Output with one decimal place
    }
}
 
// This code is contributed by guptapratik

Javascript

// Find the value of x in range [l, r] 
// for which f(x) is minimum
// f(x) = 2*(x^2) - 10*x + 2
 
function f(x) {
    return 2 * x * x - 10 * x + 2;
}
 
function findMinimum() {
    let l = -1e5;
    let r = 1e5;
    const errorLimit = 1e-9;
 
    while ((r - l) >= errorLimit) {
        let mid1 = l + (r - l) / 3.0;
        let mid2 = r - (r - l) / 3.0;
        let f_mid1 = f(mid1);
        let f_mid2 = f(mid2);
 
        if (f_mid1 < f_mid2) {
            r = mid2;
        } else if (f_mid1 > f_mid2) {
            l = mid1;
        } else if (f_mid1 === f_mid2) {
            l = mid1;
            r = mid2;
        }
    }
 
    const result = Math.round(l * 1000) / 1000; // Round to 3 decimal places
    console.log(result);
}
 
findMinimum();
 
// This code is contributed by guptapratik

Output

2.5

Time Complexity: 2 * log₃(N), where N is the range of [l, r]

Important Note: Instead of using the condition (r – l) >= 1e-9, we can simply maintain a counter = 0, for every iteration and break the loop after the counter reaches 300, because after reducing the search space 300 times, we will always get the answer correct up to 9 decimal places.

Ternary Search for Competitive Programming

Ternary search is a powerful algorithmic technique that plays a crucial role in competitive programming. This article explores the fundamentals of ternary search, idea behind ternary search with its use cases that will help solving complex optimization problems efficiently.

Table of Content

What is Ternary Search?
Why use Ternary Search?
Idea behind Ternary Search
Use Cases of Ternary Search
Practice Problems on Ternary Search for Competitive Programming:

Idea behind Ternary Search

Implementation of Ternary Search:

C++

Java

Python3

C#

Javascript

Ternary Search for Competitive Programming

Categories

Contact US

Idea behind Ternary Search

Implementation of Ternary Search:

C++

Java

Python3

C#

Javascript

Ternary Search for Competitive Programming

Similar Reads

Categories

Contact US