Ternary Search Algorithm

1. Algorithm Overview

Ternary Search is a divide-and-conquer algorithm used to find the maximum or minimum of a unimodal function (a function that increases then decreases, or vice versa) on a given interval. It works by dividing the interval into three parts and determining in which segment the extremum lies, then recursively (or iteratively) repeating on that segment.

  1. Given an interval [l, r], pick two mid-points: 
    
m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;
  2. Evaluate f(m1) and f(m2).
  3. If searching for the maximum:
    • If f(m1) < f(m2), the maximum lies in [m1, r] → set l = m1.
    • Else, the maximum lies in [l, m2] → set r = m2.
  4. Repeat until r - l is below a tolerance (for real-valued functions) or pointers cross (for discrete).

2. Time and Memory Complexity

  • Time Complexity: Each step reduces the search interval to two-thirds, so after k steps the interval is ((2/3)^k) * n. To reduce to size 1 takes O(log₃ n) steps. Equivalently O(log n).
  • Memory Complexity: O(1) extra space if implemented iteratively (only a few pointers); O(log n) stack if implemented recursively.

3. Easy Problems

3.1. Find Maximum in a Bitonic Array

A bitonic array first strictly increases then strictly decreases. Use discrete ternary search to find its peak. 

#include <iostream>
#include <vector>
using namespace std;

int ternaryPeak(const vector<int>& a) {
    int l = 0, r = a.size() - 1;
    while (l + 2 <= r) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if (a[m1] < a[m2])
            l = m1 + 1;
        else
            r = m2 - 1;
    }
    int peak = l;
    for (int i = l+1; i <= r; ++i)
        if (a[i] > a[peak])
            peak = i;
    return peak;
}

int main() {
    vector<int> arr = {1, 3, 8, 12, 9, 5, 2};
    int idx = ternaryPeak(arr);
    cout << "Peak at index " << idx
         << ", value = " << arr[idx] << endl;
    return 0;
}

3.2. Find Cube Root of a Number

Approximate the cube root of x in [0, x] using real-valued ternary search. 

#include <iostream>
#include <cmath>
using namespace std;

double cubeRoot(double x) {
    double l = 0, r = max(1.0, x), eps = 1e-6;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (fabs(m1*m1*m1 - x) < fabs(m2*m2*m2 - x))
            r = m2;
        else
            l = m1;
    }
    return (l + r) / 2;
}

int main() {
    double x = 27.0;
    cout << "Cube root of " << x << " ≈ "
         << cubeRoot(x) << endl;
    return 0;
}

4. Intermediate Problems

4.1. Maximize a Continuous Unimodal Function

Given f(x) = -(x-2)*(x-2) + 4 on [0, 4], find its maximum. 

#include <iostream>
#include <functional>
using namespace std;

double ternaryMax(function<double(double)> f, double l, double r) {
    double eps = 1e-6;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2))
            l = m1;
        else
            r = m2;
    }
    return (l + r) / 2;
}

int main() {
    auto f = [](double x) { return - (x-2)*(x-2) + 4; };
    double xm = ternaryMax(f, 0.0, 4.0);
    cout << "Maximum at x = " << xm
         << ", f(x) = " << f(xm) << endl;
    return 0;
}

4.2. Find Minimum of a Convex Function

Given g(x) = (x-1)*(x-1) + 5 on [-10, 10], find its minimum. 

#include <iostream>
#include <functional>
using namespace std;

double ternaryMin(function<double(double)> f, double l, double r) {
    double eps = 1e-6;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) > f(m2))
            l = m1;
        else
            r = m2;
    }
    return (l + r) / 2;
}

int main() {
    auto g = [](double x) { return (x-1)*(x-1) + 5; };
    double xm = ternaryMin(g, -10.0, 10.0);
    cout << "Minimum at x = " << xm
         << ", g(x) = " << g(xm) << endl;
    return 0;
}

5. Hard Problem

5.1. Optimize h(x) = x * sin(x) on [0, 10]

Find the global maximum of h(x) = x·sin(x) on [0,10] to within 1e-6 precision. 

#include <iostream>
#include <cmath>
using namespace std;

double h(double x) { return x * sin(x); }

double ternaryOptimize(double l, double r) {
    double eps = 1e-6;
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (h(m1) < h(m2))
            l = m1;
        else
            r = m2;
    }
    return (l + r) / 2;
}

int main() {
    double x_opt = ternaryOptimize(0.0, 10.0);
    cout << "Optimal x ≈ " << x_opt
         << ", h(x) ≈ " << h(x_opt) << endl;
    return 0;
}