Thuật toán: Ternary Search

Tôi còn nhớ rất rõ khoảng thời gian đầu khi bắt đầu tìm hiểu sâu hơn về lập trình thi đấu (competitive programming). Ở trường, tôi được học những thuật toán cơ bản như sắp xếp, tìm kiếm nhị phân, và một số kỹ thuật đơn giản khác. Tuy nhiên, khi bước chân vào thế giới thi đấu thuật toán, tôi mới nhận ra rằng còn rất nhiều công cụ thú vị mà chương trình học chính quy chưa hề đề cập. Một trong số đó chính là Ternary Search – một thuật toán tìm kiếm mà tôi lần đầu biết đến khi luyện giải các bài toán tối ưu hóa. Trong bài viết này, tôi muốn chia sẻ lại trải nghiệm của mình, đồng thời giải thích chi tiết về thuật toán này một cách đầy đủ và dễ hiểu.

Ternary Search là gì?

Ternary Search (tìm kiếm tam phân) là một thuật toán tìm kiếm được sử dụng chủ yếu để tìm giá trị cực đại hoặc cực tiểu của một hàm số có dạng đơn đỉnh (unimodal) trên một đoạn xác định.

Khi tôi mới nghe đến cái tên này, tôi đã nghĩ ngay rằng nó có liên quan đến việc chia làm ba phần, tương tự như cách Binary Search chia làm hai. Và đúng là như vậy. Nếu Binary Search chia khoảng tìm kiếm thành hai phần, thì Ternary Search chia nó thành ba phần bằng cách chọn hai điểm phân chia.

Ý tưởng cốt lõi

Giả sử tôi có một hàm số f(x), và tôi biết rằng hàm này là unimodal, nghĩa là:

• Hoặc là tăng dần rồi giảm dần (có một đỉnh cực đại).
• Hoặc giảm dần rồi tăng dần (có một đáy cực tiểu).

Ternary Search hoạt động bằng cách:

1. Chọn hai điểm m_1 và m_2 sao cho: m_1 = l + (r - l) / 3, m_2 = r - (r - l) / 3
2. So sánh giá trị của hàm tại hai điểm này:
3. Nếu f(m_1) < f(m_2), thì cực trị nằm ở đoạn [m_1, r]
4. Ngược lại, cực trị nằm ở đoạn [l, m_2]
5. Lặp lại quá trình cho đến khi đoạn tìm kiếm đủ nhỏ.

Điểm quan trọng là tôi không tìm một giá trị cụ thể giống như Binary Search, mà là tìm vị trí tối ưu (nơi hàm đạt giá trị lớn nhất hoặc nhỏ nhất).

Khi nào thì áp dụng Ternary Search?

Đây là câu hỏi mà chính tôi cũng từng bối rối khi mới học. Không phải bài toán nào cũng dùng được Ternary Search, và việc nhận diện bài toán phù hợp là vô cùng quan trọng.

Điều kiện áp dụng

Tôi thường áp dụng Ternary Search khi:

1. Hàm mục tiêu là unimodal: Đây là điều kiện tiên quyết. Nếu hàm không có dạng tăng rồi giảm (hoặc ngược lại), thuật toán có thể cho kết quả sai.
2. Không thể giải bằng công thức trực tiếp: Nhiều bài toán tối ưu có thể dùng đạo hàm hoặc công thức toán học, nhưng trong competitive programming, tôi thường gặp các hàm không rõ ràng hoặc khó phân tích.
3. Hàm có thể tính được nhanh: Mỗi lần lặp, tôi cần tính giá trị của hàm tại hai điểm. Nếu hàm tính quá chậm, tổng thời gian sẽ lớn.

Sự khác biệt giữa Ternary Search và Binary Search

Khi mới học Ternary Search, tôi thường so sánh với Binary Search để hiểu rõ bản chất.

Binary Search

• Dùng để tìm kiếm trong một dãy đã được sắp xếp.
• Mỗi bước chia không gian tìm kiếm thành 2 phần.
• Dựa trên tính chất đơn điệu (monotonic) của điều kiện.

Ternary Search

• Dùng để tối ưu hóa hàm số.
• Mỗi bước chia không gian thành 3 phần.
• Dựa trên tính chất unimodal của hàm.

So sánh trực quan

Khi nào dùng Binary Search, khi nào dùng Ternary Search?

Đây là phần mà tôi từng mất khá nhiều thời gian để hiểu rõ.

Dùng Binary Search khi

• Tôi có một hàm điều kiện đơn điệu
• Ví dụ:
  • Tìm giá trị nhỏ nhất thỏa mãn điều kiện
  • Kiểm tra một ngưỡng (threshold)

Một pattern quen thuộc là:

“Nếu một giá trị x là hợp lệ, thì mọi giá trị lớn hơn (hoặc nhỏ hơn) cũng hợp lệ”

Dùng Ternary Search khi

• Tôi cần tìm giá trị tối ưu (max/min) của một hàm
• Hàm này:
  • Không đơn điệu
  • Nhưng có duy nhất một cực trị

So sánh cảm giác khi dùng

• Binary Search giống như tôi hỏi đúng/sai và loại trừ một nửa
• Ternary Search giống như tôi so sánh hai lựa chọn và quyết định hướng đi tốt hơn

Độ phức tạp của thuật toán

Ternary Search, tương tự Binary Search, hoạt động bằng cách thu hẹp không gian tìm kiếm theo cấp số nhân.

• Mỗi vòng lặp giảm khoảng tìm kiếm còn 2/3 ban đầu
• Tổng số lần lặp là: O(\log n)

Với biến thực

Nếu tôi làm việc với số thực:

• Tôi lặp cho đến khi r - l < sai số
• Thường cần khoảng 100–200 vòng lặp để đạt độ chính xác cao

Trong thực tế, tôi thấy hầu hết bài toán tối ưu trong competitive programming đều áp dụng ternary search với biến rời rạc và thường dùng brute force khi khoảng cực trị đủ nhỏ.

Thuật toán cụ thể

Dưới đây là pseudocode tìm cực đại. Với bài toán tìm cực tiểu, thuật toán cũng tương tự như vậy nhưng thay đổi điều kiện so sánh một chút.

function ternary_search(l, r):
    while (r - l) > eps:
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3

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

    return (l + r) / 2

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ị các thẻ được lấy ra.

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) → không thể dùng binary search
• Hàm có dạng ∩ (tăng rồi giảm) → ternary search rất phù hợp
• 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ố lưu ý quan trọng từ kinh nghiệm cá nhân

Sau khi sử dụng Ternary Search trong nhiều bài thi, tôi rút ra một vài kinh nghiệm thực tế:

Luôn kiểm tra tính unimodal

Nếu hàm không có dạng đơn đỉnh, kết quả có thể sai hoàn toàn. Tôi từng mắc lỗi này và mất rất nhiều thời gian debug.

Chọn số vòng lặp hợp lý

• Với số thực: ~100 vòng là đủ
• Không nên phụ thuộc hoàn toàn vào epsilon

Cẩn thận với sai số

Tôi thường trả về:

(l + r) / 2

hoặc lấy giá trị tốt nhất trong khoảng cuối cùng.

Với số nguyên

Ternary Search trên số nguyên cần xử lý khác một chút, vì khoảng có thể rất nhỏ. Tôi thường chuyển sang duyệt brute-force khi đoạn còn vài phần tử.

Kết luận

Ternary Search là một thuật toán mà tôi tin rằng bất kỳ ai theo đuổi competitive programming đều nên biết. Nó không phải là kiến thức phổ thông trong trường học, nhưng lại xuất hiện khá nhiều trong các bài toán tối ưu.

Thông qua việc học và áp dụng Ternary Search, tôi không chỉ có thêm một công cụ mạnh mẽ, mà còn học được cách nhìn nhận bài toán theo hướng linh hoạt hơn.