Ternary Search

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 16:28

Ternary Search tìm điểm cực trị (min hoặc max) của hàm unimodal (lồi hoặc lõm) trên đoạn $[l o, h i]$ trong $O (\log N)$ — tương tự binary search nhưng cho hàm không đơn điệu.

Điều kiện áp dụng: Hàm $f$ phải unimodal — tức là tăng rồi giảm (hoặc giảm rồi tăng), có đúng một điểm cực trị.

Ternary Search trên số thực

// Tìm x trong [lo, hi] tối thiểu hóa f(x) (hàm lồi)
double ternary_search_real(double lo, double hi,
                            function<double(double)> f) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) hi = m2;
        else               lo = m1;
    }
    return (lo + hi) / 2;
}

// Tìm max (hàm lõm): đổi dấu so sánh
double ternary_search_max(double lo, double hi,
                           function<double(double)> f) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) > f(m2)) hi = m2;
        else               lo = m1;
    }
    return (lo + hi) / 2;
}

Số vòng lặp: 200 vòng cho độ chính xác $\approx (2 / 3)^{200} \cdot (h i - l o) \approx 10^{- 35}$ . Với bài cần $10^{- 9}$ thì 100 vòng đủ.

Ternary Search trên số nguyên

Với hàm unimodal trên số nguyên, cần thận trọng hơn:

// Tìm x nguyên trong [lo, hi] tối thiểu hóa f(x)
int ternary_search_int(int lo, int hi,
                        function<long long(int)> f) {
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) <= f(m2)) hi = m2;
        else                lo = m1;
    }
    // Kiểm tra từng điểm còn lại
    int ans = lo;
    for (int x = lo; x <= hi; x++)
        if (f(x) < f(ans)) ans = x;
    return ans;
}

Ví dụ 1: Tìm điểm trên đường thẳng gần nhất với tập điểm

// Tối thiểu hóa tổng khoảng cách từ điểm (x, f(x)) đến tập điểm
// f(x) = sum of distances là hàm lồi theo x
double best_x = ternary_search_real(x_min, x_max, [&](double x) {
    double total = 0;
    for (auto [px, py] : points)
        total += hypot(x - px, line_y(x) - py);
    return total;
});

Ví dụ 2: Tối ưu hóa trên đa giác lồi

Tìm điểm xa nhất/gần nhất với một điểm truy vấn trên convex hull:

// Hàm khoảng cách từ điểm hull[i] đến điểm P là unimodal theo i
// => Ternary search trên mảng hull[]
int n = hull.size();
int lo = 0, hi = n - 1;
while (hi - lo > 2) {
    int m1 = lo + (hi - lo) / 3;
    int m2 = hi - (hi - lo) / 3;
    if (dist(hull[m1], P) < dist(hull[m2], P)) lo = m1;
    else hi = m2;
}

Ví dụ 3: Tìm thời điểm tối ưu

Bài toán: có $n$ máy, máy $i$ bắt đầu sản xuất sau $t_{i}$ giây, tốc độ $r_{i}$ sản phẩm/giây. Tìm thời điểm $T$ để sản xuất $K$ sản phẩm nhanh nhất — hàm "tổng sản phẩm tại $T$ " là hàm tăng dần, binary search trên $T$ .

So sánh với Binary Search

	Binary Search	Ternary Search
Điều kiện	Hàm đơn điệu	Hàm unimodal
Tìm	Giá trị cụ thể / ngưỡng	Điểm cực trị
Số lần thu hẹp	Chia đôi mỗi bước	Bỏ $1 / 3$ mỗi bước
Độ phức tạp	$O (\log N)$	$O (\log N)$

Mẹo: Nhiều bài ternary search trên số thực có thể viết lại thành binary search trên đạo hàm $f^{'} (x)$ (tìm điểm $f^{'} (x) = 0$ ) nếu đạo hàm có dạng đơn điệu.

Khi nào dùng Ternary Search?

Tối ưu hóa hàm liên tục lồi/lõm (geometry, physics simulation).
Tìm max/min trên mảng nguyên có dạng unimodal.
Kết hợp với convex hull để tìm điểm xa nhất $O (\log N)$ .
Bài "tìm thời điểm/vị trí tối ưu" mà hàm mục tiêu unimodal.

Bình luận

Không có bình luận tại thời điểm này.