Ternary search adalah algoritma untuk menemukan maksimum atau minimum dari sebuah fungsi unimodal — fungsi yang naik lalu turun (atau turun lalu naik) pada domain kontigu. Berbeda dengan binary search yang bekerja pada data terurut, ternary search bekerja pada data dengan struktur “puncak tunggal” atau “lembah tunggal”. Aplikasi klasiknya: optimasi parameter diskret (misalnya konstanta dalam rumus fisika), pencarian titik maksimum pada graf fungsi polinom, atau pencarian titik balik pada array bitonic. Pada Chapter ini kita akan mempelajari mekanisme pembagian tiga, perbandingannya dengan binary search pada fungsi unimodal, serta analisis kompleksitasnya.

Fungsi Unimodal #

Fungsi f(x) disebut unimodal pada interval [lo, hi] bila ada satu titik x* sehingga:

  • Untuk maksimum: f monoton naik di [lo, x*] dan monoton turun di [x*, hi].
  • Untuk minimum: f monoton turun di [lo, x*] dan monoton naik di [x*, hi].

Bila f memiliki banyak puncak lokal (multimodal), ternary search tidak menjamin menemukan global optimum.

Aturan dan Mekanisme #

Diberikan fungsi unimodal f pada [lo, hi], cari x* yang memaksimalkan (atau meminimalkan) f.

  1. Pilih dua titik dalam: m1 = lo + (hi - lo) / 3 dan m2 = hi - (hi - lo) / 3.
  2. Bandingkan f(m1) dan f(m2):
    • Untuk maksimum: bila f(m1) < f(m2), puncak pasti di [m1, hi] → lo = m1. Sebaliknya → hi = m2.
    • Untuk minimum: bila f(m1) > f(m2), lembah pasti di [m1, hi] → lo = m1. Sebaliknya → hi = m2.
  3. Ulangi hingga hi - lo cukup kecil (presisi tercapai).

Setiap iterasi membuang sepertiga ruang, sehingga jumlah iterasi sekitar log_{1.5}(n).

Implementasi pada Domain Diskret #

Kode: Ternary Search Diskret untuk Maksimum #

cpp 
#include <iostream>
#include <vector>
#include <functional>

long long ternary_search_max(long long lo, long long hi,
                             const std::function<long long(long long)>& f)
{
    while (hi - lo > 2) {
        long long m1 = lo + (hi - lo) / 3;
        long long m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;
        else                 hi = m2;
    }
    // Iterasi sisa kecil: cari manual
    long long best = f(lo), best_x = lo;
    for (long long x = lo + 1; x <= hi; ++x) {
        long long v = f(x);
        if (v > best) { best = v; best_x = x; }
    }
    return best_x;
}

int main() {
    // f(x) = -(x-4)^2 + 10, maksimum di x=4, f(4)=10
    auto f = [](long long x) { return -(x - 4) * (x - 4) + 10; };
    long long x = ternary_search_max(0, 10, f);
    std::cout << "x* = " << x << ", f(x*) = " << f(x) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
x* = 4, f(x*) = 10
  1. Baris while (hi - lo > 2): berhenti saat rentang tinggal ≤ 3 nilai; terlalu kecil untuk dibagi tiga secara bermakna.
  2. Baris m1 = lo + (hi - lo) / 3; m2 = hi - (hi - lo) / 3;: dua titik sepertiga dari ujung.
  3. Baris if (f(m1) < f(m2)) lo = m1;: untuk maksimum, bila f(m2) lebih besar, puncak pasti di kanan m1. Kita geser lo ke m1 (bukan m1 + 1 — m1 sendiri bisa jadi optimum).
  4. Baris else hi = m2;: cermin — geser hi ke m2.
  5. Loop eksplisit akhir: saat rentang kecil, cek semua kandidat untuk memastikan akurasi.

Implementasi pada Domain Kontinu #

Untuk domain kontinu (floating point), kita iterasi hingga selisih hi - lo lebih kecil dari toleransi eps.

Kode: Ternary Search Kontinu #

cpp 
#include <iostream>
#include <cmath>
#include <functional>

double ternary_search_max_double(double lo, double hi,
                                 const std::function<double(double)>& f,
                                 int max_iter = 200)
{
    for (int i = 0; i < max_iter; ++i) {
        double m1 = lo + (hi - lo) / 3.0;
        double m2 = hi - (hi - lo) / 3.0;
        if (f(m1) < f(m2)) lo = m1;
        else                 hi = m2;
        if (hi - lo < 1e-9) break;
    }
    return (lo + hi) / 2.0;
}

int main() {
    // f(x) = sin(x) * exp(-0.1 * x^2) pada [0, 6]
    auto f = [](double x) { return std::sin(x) * std::exp(-0.1 * x * x); };
    double x = ternary_search_max_double(0.0, 6.0, f);
    std::cout << "x* = " << x << ", f(x*) = " << f(x) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
x* = 1.31384, f(x*) = 0.813833
  1. Baris for (int i = 0; i < max_iter; ++i): iterasi terbatas. 200 iterasi cukup untuk presisi 1e-9 pada hampir semua fungsi praktis.
  2. Baris double m1 = lo + (hi - lo) / 3.0;: pembagian titik mengambang, bukan pembulatan integer.
  3. Baris if (hi - lo < 1e-9) break;: kriteria konvergensi alternatif berbasis lebar interval.
  4. Baris return (lo + hi) / 2.0;: midpoint sebagai estimasi optimum.
  5. Hasil x* ≈ 1.31384: optimum lokal fungsi sin(x) * exp(-0.1 x²) di sekitar x = 1.31, nilai f ≈ 0.814. Fungsi unimodal pada [0, 6] — naik dari 0, puncak di ~1.31, lalu turun.

Ternary Search vs Binary Search pada Fungsi Unimodal #

Pertanyaan menarik: mana lebih cepat untuk fungsi unimodal diskret — ternary search atau binary search dengan predikat?

AspekTernary SearchBinary Search (derivatif)
Titik evaluasi per iterasi2 (m1, m2)1 (titik + neighbor)
Penyusutan per iterasi2/31/2
Iterasi untuk presisi εlog_{1.5}(n)log_2(n)
Evaluasi fungsi total2 × log_{1.5}(n)2 × log_2(n)
Rasio evaluasi2 / log_2(1.5) ≈ 3.421

Ternyata binary search pada turunan fungsi (bandingkan f(m) vs f(m+1)) membutuhkan lebih sedikit evaluasi total. Ternary search unggul bila f sangat mahal dievaluasi dan tidak bisa di-interval seperti pada soal interaktif.

Verifikasi Numerik: Akar Persamaan #

Misalkan kita ingin mencari titik minimum dari f(x) = (x - 3.5)^2 + 2 pada rentang [0, 10]. Minimum seharusnya di x = 3.5 dengan f(x) = 2.

Kode: Verifikasi Presisi #

cpp 
#include <iostream>
#include <cmath>
#include <functional>

double ternary_min(double lo, double hi,
                   const std::function<double(double)>& f,
                   int max_iter = 100)
{
    for (int i = 0; i < max_iter; ++i) {
        double m1 = lo + (hi - lo) / 3.0;
        double m2 = hi - (hi - lo) / 3.0;
        if (f(m1) > f(m2)) lo = m1;  // min: lembah di kanan
        else                 hi = m2;
    }
    return (lo + hi) / 2.0;
}

int main() {
    auto f = [](double x) { return (x - 3.5) * (x - 3.5) + 2; };
    double x = ternary_min(0.0, 10.0, f);
    std::cout << "minimum di x* = " << x << '\n';
    std::cout << "f(x*) = " << f(x) << '\n';
    std::cout << "error |x - 3.5| = " << std::abs(x - 3.5) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
minimum di x* = 3.5
f(x*) = 2
error |x - 3.5| = 1.49012e-08
  1. Baris if (f(m1) > f(m2)) lo = m1;: untuk minimum, bila f(m1) lebih besar, lembah pasti di kanan m1. Geser lo ke m1.
  2. Baris else hi = m2;: cermin.
  3. Hasil x* = 3.5: konvergen ke 3.5 dengan toleransi floating point ~1.5e-8.
  4. Error kecil: residu 1.49e-08 berasal dari representasi double — tidak signifikan untuk aplikasi praktis.

Aplikasi: Maksimum pada Array Bitonic #

Array bitonic adalah array yang naik lalu turun (mirip fungsi unimodal diskret). Ternary search dapat menemukan puncak.

Kode: Puncak Array Bitonic #

cpp 
#include <iostream>
#include <vector>

int peak_index(const std::vector<int>& a) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (a[m1] < a[m2]) lo = m1;
        else                 hi = m2;
    }
    int best = lo;
    for (int i = lo + 1; i <= hi; ++i)
        if (a[i] > a[best]) best = i;
    return best;
}

int main() {
    std::vector<int> a = {1, 3, 7, 12, 9, 5, 2};
    int p = peak_index(a);
    std::cout << "puncak di indeks " << p
              << ", nilai a[" << p << "] = " << a[p] << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
puncak di indeks 3, nilai a[3] = 12
  1. Baris a[m1] < a[m2]: untuk maksimum pada array bitonic, bila a[m2] lebih besar, puncak pasti di kanan m1.
  2. Loop eksplisit akhir: saat hi - lo ≤ 2, cek semua kandidat. Tiga elemen terlalu sedikit untuk dibagi tiga secara bermakna.
  3. Hasil indeks 3: elemen 12 adalah puncak. Sesuai.

Ringkasan #

  • Ternary search bekerja pada fungsi unimodal — naik lalu turun, atau turun lalu naik.
  • Setiap iterasi mengevaluasi dua titik m1 dan m2 pada sepertiga interval, lalu membuang sepertiga ruang.
  • Kompleksitas O(log_{1.5} n) iterasi, O(2 log_{1.5} n) evaluasi fungsi.
  • Untuk domain diskret, tambahkan loop eksplisit saat rentang kecil.
  • Untuk domain kontinu, iterasi hingga hi - lo < eps atau max_iter tercapai.
  • Untuk fungsi unimodal yang murah dievaluasi, binary search pada turunan biasanya lebih efisien (2 log₂ n vs 3.42 log₂ n).