Thuật toán: Ternary Search

Trong quá trình học và thi lập trình, có những bài toán tưởng chừng đơn giản nhưng tôi từng “vật lộn” với chúng. Dạng bài rất quen thuộc:

Không phải tìm giá trị thỏa điều kiện… mà là tìm giá trị “tốt nhất”

Đây chính là lúc các thuật toán tìm kiếm tối ưu phát huy sức mạnh. Trong nhiều bài toán, binary search (tìm kiếm nhị phân) không áp dụng được. Và đó là lúc tôi biết đến Ternary Search (tìm kiếm tam phân).

Ternary Search là gì?

Ternary Search (tìm kiếm tam phân) là thuật toán dùng để:

Tìm giá trị cực đại (max) hoặc cực tiểu (min) của một hàm số

Điều kiện quan trọng nhất: hàm unimodal

Hàm phải là unimodal. Một hàm được gọi là unimodal nếu nó chỉ có một cực trị duy nhất trên đoạn xét. Hàm unimodal có hai dạng điển hình

Tăng → đạt đỉnh → giảm

   ^
  / \
 /   \
/     \

Giảm → đạt đáy → tăng

\     /
 \   /
  \ /
   v

Nói chung, hàm chỉ đổi hướng 1 lần là hàm unimodal. Hàm không phải unimodal nếu có nhiều cực trị, hoặc hàm dao động nhiều lần.

Khi nào dùng Ternary Search?

Nên dùng khi

• Bài toán yêu cầu:
  • Tìm max / min
  • Tối ưu chi phí, khoảng cách, thời gian
• Có thể xây dựng hàm f(x) có dạng unimodal

Ternary Search vs Binary Search

Thuật toán binary search quen thuộc với nhiều người. Nhưng chỉ có thể áp dụng trong trường hợp: Nếu X thỏa mãn điều kiện thì X-1 cũng thỏa mãn điều kiện còn X+1 thì không. Nghĩa là X chính là “điểm chuyển”, chia không gian thành 2 vùng ngược nhau.

Đó là tính chất quan trọng nhất: binary search chỉ áp dụng được khi hàm phải monotonic (đơn điệu).

Nhưng nhiều bài không monotonic

Ví dụ:

f(x) = -x² + 4x + 5

Giá trị:

x: 0   1   2   3   4   5
f: 5   8   9   8   5   0

Tăng rồi giảm → không binary search được. Nhưng là unimodal → ternary search

Ý tưởng của Ternary Search

Chia đoạn [l, r] thành 3 phần:

m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;

So sánh:

Tìm max:

if (f(m1) < f(m2))
    l = m1;
else
    r = m2;

• Nếu f(m1) < f(m2) → đi về phía m2
• Ngược lại → đi về phía m1

Tìm min:

if (f(m1) > f(m2))
    l = m1;
else
    r = m2;

Lưu ý rằng, Ternary Search không đưa ra được điểm cực trị, mà chỉ có thể đưa ra khoảng cực trị mà thôi. Khoảng cực trị này sẽ giảm dần và đến mức nào đó, Ternary Search không thể tiếp tục được nữa.

Lúc này, có hai lựa chọn: Nếu khoảng cực trị đủ nhỏ, dưới sai số cho phép thì có thể dừng luôn và trả về kết quả (có thể tính toán vài lần để chọn ra giá trị tốt nhất). Lựa chọn thứ hai, hay gặp trong contest, đó là không gian tìm kiếm là hữu hạn, các biến là số nguyên nên có thể brute force với khoảng cực trị này để tìm ra giá trị tốt nhất.

Ví dụ

Bài toán 1

Tìm max của: f(x) = -x² + 4x + 5 trên đoạn [0, 5]

Lời giải:

#include <bits/stdc++.h>
using namespace std;

double f(double x) {
    return -x * x + 4 * x + 5;
}

double ternary(double l, double r) {
    for (int i = 0; i < 100; i++) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;

        if (f(m1) < f(m2))
            l = m1;
        else
            r = m2;
    }
    return f(l);
}

int main() {
    cout << fixed << setprecision(6);
    cout << ternary(0, 5);
}

Bài toán 2: Bài E Codeforces round 1043 (Div. 3)

Bài toán đầy đủ ở đây.

Đề bài

Bài toán tương đối dài, nhưng có thể tóm tắt như sau:

• Vadim có n thẻ: a[i]
• Kostya có m thẻ: b[i]

Có q truy vấn, với mỗi truy vấn:

• Chọn tổng cộng z thẻ
  • Từ Vadim không quá x thẻ
  • Từ Kostya không quá y thẻ

Mục tiêu: tối đa tổng giá trị

Phân tích

Giả sử chọn:

• k thẻ từ Vadim
• z - k thẻ từ Kostya

Điều kiện:

0 ≤ k ≤ x
0 ≤ z - k ≤ y

→ Suy ra:

max(0, z - y) ≤ k ≤ min(z, x)

Ý tưởng chính

• Sắp xếp a, b giảm dần
• Tính prefix sum:

pa[i] = tổng i phần tử lớn nhất của a
pb[i] = tổng i phần tử lớn nhất của b

Xây dựng hàm

f(k) = pa[k] + pb[z - k]

Đây chính là hàm cần tối ưu. Nếu như duyệt mọi giá trị của k (độ phức tạp O(n)) thì chắc chắn chương trình sẽ vượt quá thời gian cho phép. Cần phải tìm cách tối ưu thuật toán. Ta nhận ra tính chất quan trọng:

• pa[k] tăng chậm dần
• pb[z-k] giảm dần

Tổng hai hàm này tạo thành hàm dạng unimodal (tăng → đạt đỉnh → giảm)

Vì sao dùng ternary search?

• Không có điều kiện monotonic (Không có “điểm chuyển” rõ ràng) → ❌ binary search
• Hàm có dạng ∩ (tăng rồi giảm) → ✅ ternary search
• Nhưng ternary search chỉ có thể tìm ra khoảng tối ưu, sau đó phải brute force để tìm ra kết quả

Code hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m, q;
        cin >> n >> m >> q;

        vector<int> a(n), b(m);
        for (auto& x : a) cin >> x;
        for (auto& x : b) cin >> x;
        sort(a.begin(), a.end(), greater<>());
        sort(b.begin(), b.end(), greater<>());

        vector<int64_t> pa(n + 1, 0), pb(m + 1, 0);
        for (int i = 0; i < n; i++) pa[i + 1] = pa[i] + a[i];
        for (int i = 0; i < m; i++) pb[i + 1] = pb[i] + b[i];

        while (q--) {
            int x, y, z;
            cin >> x >> y >> z;

            int l = max(0, z - y);
            int r = min(z, x);

            if (l > r) {
                cout << 0 << "\n";
                continue;
            }

            auto f = [&](int k) { return pa[k] + pb[z - k]; };

            while (r - l > 3) {
                int m1 = l + (r - l) / 3;
                int m2 = r - (r - l) / 3;

                if (f(m1) < f(m2))
                    l = m1;
                else
                    r = m2;
            }

            int64_t ans = 0;
            for (int k = l; k <= r; k++) ans = max(ans, f(k));
            cout << ans << "\n";
        }
    }

    return 0;
}

Một số sai lầm phổ biến

• Dùng ternary search khi hàm không unimodal → kết quả sai mà khó phát hiện
• Nhầm với binary search → cố ép bài theo điều kiện monotonic
• Chọn khoảng tìm kiếm không đủ lớn → mất nghiệm đúng

Kết luận

Binary Search áp dụng khi monotonic còn Ternary SearchSearch áp dụng khi có 1 cực trị (unimodal)

Khi gặp bài toán:

• Không có điều kiện đúng/sai rõ ràng
• Chỉ có tối ưu
• Hàm tăng → giảm hoặc ngược lại

→ Rất có thể là Ternary Search