Skip to content

Bài 55: Ternary Search - Tìm kiếm tam phân

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms, e-maxx

Bản chất vấn đề

Phát biểu bài toán

Cho một hàm số \(f(x)\) xác định trên đoạn \([l, r]\). Tìm giá trị \(x^*\) sao cho \(f(x^*)\) đạt giá trị lớn nhất (hoặc nhỏ nhất).

Điều kiện tiên quyết: Hàm \(f\) phải là hàm unimodal (đơn đỉnh), tức là tồn tại đúng một điểm cực trị duy nhất trên \([l, r]\).

Hàm unimodal là gì?

Một hàm \(f(x)\) trên đoạn \([l, r]\) được gọi là unimodal nếu tồn tại đúng một điểm \(c \in [l, r]\) sao cho:

  • Trường hợp tìm MAX: \(f\) tăng liên tục trên \([l, c]\) và giảm liên tục trên \([c, r]\). Điểm \(c\) là đỉnh (global maximum).
  • Trường hợp tìm MIN: \(f\) giảm liên tục trên \([l, c]\) và tăng liên tục trên \([c, r]\). Điểm \(c\) là đáy (global minimum).
graph LR
    subgraph "Hàm lồi - tìm MAX"
    A["f tăng"] --> B["Đỉnh c"] --> C["f giảm"]
    end
    subgraph "Hàm lõm - tìm MIN"
    D["f giảm"] --> E["Đáy c"] --> F["f tăng"]
    end

Tại sao Binary Search không giải được?

Tiêu chí Binary Search Ternary Search
Yêu cầu hàm Monotonic (đơn điệu) Unimodal (đơn đỉnh)
Mục tiêu Tìm vị trí trong mảng đã sắp xếp Tìm max/min của hàm
Số điểm so sánh mỗi bước 1 2
Số phần bị loại mỗi bước \(\frac{1}{2}\) \(\frac{1}{3}\)

Hàm monotonic luôn tăng hoặc luôn giảm, trong khi hàm unimodal tăng rồi giảm (hoặc ngược lại). Binary Search chỉ hoạt động trên hàm monotonic, nên không thể tìm đỉnh của hàm unimodal.

Ví dụ trực quan

Hàm \(f(x) = -(x - 3)^2 + 10\) là unimodal với đỉnh tại \(x = 3\), \(f(3) = 10\).

\(x\) 0 1 2 3 4 5 6
\(f(x)\) 1 6 9 10 9 6 1

Hàm tăng từ \(x = 0\) đến \(x = 3\), sau đó giảm. Đỉnh duy nhất tại \(x = 3\).

Tư duy cốt lõi

Ý tưởng chính

Chia đoạn \([l, r]\) thành 3 phần bằng hai điểm \(m_1\) và \(m_2\):

\[m_1 = l + \frac{r - l}{3}, \quad m_2 = r - \frac{r - l}{3}\]

So sánh \(f(m_1)\) và \(f(m_2)\) để loại bỏ \(\frac{1}{3}\) phạm vi tìm kiếm:

  • Nếu \(f(m_1) < f(m_2)\): đỉnh không thể nằm trong đoạn \([l, m_1)\), thu hẹp về \([m_1, r]\).
  • Nếu \(f(m_1) > f(m_2)\): đỉnh không thể nằm trong đoạn \((m_2, r]\), thu hẹp về \([l, m_2]\).
  • Nếu \(f(m_1) = f(m_2)\): đỉnh nằm trong \([m_1, m_2]\).
graph TD
    A["Chia [l, r] thành 3 phần\nm1 = l + (r-l)/3\nm2 = r - (r-l)/3"] --> B{"So sánh f(m1) và f(m2)"}
    B -->|"f(m1) < f(m2)"| C["Loại [l, m1)\n[l, r] = [m1, r]"]
    B -->|"f(m1) > f(m2)"| D["Loại (m2, r]\n[l, r] = [l, m2]"]
    B -->|"f(m1) = f(m2)"| E["Thu hẹp [m1, m2]"]
    C --> F{"r - l đủ nhỏ?"}
    D --> F
    E --> F
    F -->|"Chưa"| A
    F -->|"Rồi"| G["Trả về (l + r) / 2"]

Bước lặp chi tiết

Mỗi lần lặp, ta gọi \(f\) đúng 2 lần (tại \(m_1\) và \(m_2\)). Sau \(k\) lần lặp, độ dài đoạn còn lại là:

\[\text{length}_k = \left(\frac{2}{3}\right)^k \cdot (r - l)\]

Với miền giá trị \([0, 10^9]\), sau 200 lần lặp độ dài còn lại xấp xỉ \(10^{-35}\), đủ cho độ chính xác double.

Ternary Search trên số nguyên

Khi \(x\) chỉ nhận giá trị nguyên, việc chia đôi liên tục có thể dẫn đến vòng lặp vô hạn khi \(m_1 = m_2\). Giải pháp: dừng sớm khi \(r - l \leq 3\) và brute force đoạn còn lại.

Lý do dừng tại 3: Khi \(r - l \leq 3\), đoạn có tối đa 4 phần tử. Brute force 4 phần tử mất \(O(1)\), không ảnh hưởng độ phức tạp.

Code: Ternary Search trên số thực

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

double f(double x) {
    return -(x - 3.0) * (x - 3.0) + 10.0;
}

int main() {
    double l = 0.0, r = 10.0;
    for (int iter = 0; iter < 200; iter++) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) < f(m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
    double x = (l + r) / 2.0;
    printf("MAX tai x = %.6f, f(x) = %.6f\n", x, f(x));
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def f(x):
    return -(x - 3.0) ** 2 + 10.0

l, r = 0.0, 10.0
for _ in range(200):
    m1 = l + (r - l) / 3.0
    m2 = r - (r - l) / 3.0
    if f(m1) < f(m2):
        l = m1
    else:
        r = m2

x = (l + r) / 2.0
print(f"MAX tai x = {x:.6f}, f(x) = {f(x):.6f}")

Code: Ternary Search trên số nguyên

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

int f(int x) {
    return -(x - 5) * (x - 5) + 20;
}

int main() {
    int l = 0, r = 100;
    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;
        }
    }
    int best = l;
    for (int i = l + 1; i <= r; i++) {
        if (f(i) > f(best)) best = i;
    }
    printf("MAX tai x = %d, f(x) = %d\n", best, f(best));
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def f(x):
    return -(x - 5) ** 2 + 20

l, r = 0, 100
while r - l > 3:
    m1 = l + (r - l) // 3
    m2 = r - (r - l) // 3
    if f(m1) < f(m2):
        l = m1
    else:
        r = m2

best = l
for i in range(l + 1, r + 1):
    if f(i) > f(best):
        best = i
print(f"MAX tai x = {best}, f(x) = {f(best)}")

Code: Ternary Search tìm MIN (hàm lõm)

Khi hàm \(f\) là lõm (giảm rồi tăng), ta đảo điều kiện so sánh để tìm đáy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int n;
vector<double> a;

double f(double p) {
    double sum = 0;
    for (int i = 0; i < n; i++) sum += abs(a[i] - p);
    return sum;
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    double l = *min_element(a.begin(), a.end());
    double r = *max_element(a.begin(), a.end());

    for (int iter = 0; iter < 200; iter++) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) > f(m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
    double p = (l + r) / 2.0;
    printf("Diem toi uu: %.6f, tong khoang cach: %.6f\n", p, f(p));
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def solve():
    n = int(input())
    a = list(map(float, input().split()))

    def f(p):
        return sum(abs(x - p) for x in a)

    l, r = min(a), max(a)
    for _ in range(200):
        m1 = l + (r - l) / 3.0
        m2 = r - (r - l) / 3.0
        if f(m1) > f(m2):
            l = m1
        else:
            r = m2

    p = (l + r) / 2.0
    print(f"Diem toi uu: {p:.6f}, tong khoang cach: {f(p):.6f}")

solve()

Code: Ternary Search 2D

Khi hàm \(f(x, y)\) là unimodal trong cả hai biến, lồng 2 vòng Ternary Search: vòng ngoài tìm \(x\), vòng trong tìm \(y\) tốt nhất cho mỗi \(x\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

double f(double x, double y) {
    return -(x - 2) * (x - 2) - (y - 3) * (y - 3) + 10;
}

double search_y(double x, double ly, double ry) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = ly + (ry - ly) / 3.0;
        double m2 = ry - (ry - ly) / 3.0;
        if (f(x, m1) < f(x, m2)) ly = m1;
        else ry = m2;
    }
    return (ly + ry) / 2.0;
}

int main() {
    double lx = -10, rx = 10, ly = -10, ry = 10;
    for (int iter = 0; iter < 200; iter++) {
        double x1 = lx + (rx - lx) / 3.0;
        double x2 = rx - (rx - lx) / 3.0;
        double y1 = search_y(x1, ly, ry);
        double y2 = search_y(x2, ly, ry);
        if (f(x1, y1) < f(x2, y2)) lx = x1;
        else rx = x2;
    }
    double best_x = (lx + rx) / 2.0;
    double best_y = search_y(best_x, ly, ry);
    printf("MAX tai (%.6f, %.6f), f = %.6f\n", best_x, best_y, f(best_x, best_y));
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def f(x, y):
    return -(x - 2) ** 2 - (y - 3) ** 2 + 10

def search_y(x, ly, ry):
    for _ in range(200):
        m1 = ly + (ry - ly) / 3.0
        m2 = ry - (ry - ly) / 3.0
        if f(x, m1) < f(x, m2):
            ly = m1
        else:
            ry = m2
    return (ly + ry) / 2.0

lx, rx, ly, ry = -10, 10, -10, 10
for _ in range(200):
    x1 = lx + (rx - lx) / 3.0
    x2 = rx - (rx - lx) / 3.0
    y1 = search_y(x1, ly, ry)
    y2 = search_y(x2, ly, ry)
    if f(x1, y1) < f(x2, y2):
        lx = x1
    else:
        rx = x2

best_x = (lx + rx) / 2.0
best_y = search_y(best_x, ly, ry)
print(f"MAX tai ({best_x:.6f}, {best_y:.6f}), f = {f(best_x, best_y):.6f}")

Phân tích tính đúng đắn

Chứng minh thuật toán luôn hội tụ

Định lý: Nếu \(f\) là unimodal trên \([l, r]\) với đỉnh tại \(c\), thì sau mỗi bước lặp, đỉnh \(c\) luôn nằm trong đoạn \([l, r]\) mới.

Chứng minh cho trường hợp tìm MAX:

Xét một bước lặp với \(m_1 < m_2\). Vì \(f\) unimodal với đỉnh \(c\):

  • Nếu \(f(m_1) < f(m_2)\): đỉnh \(c\) phải nằm bên phải \(m_1\) (vì \(f\) còn đang tăng). Vậy \(c \in [m_1, r]\). Gán \(l = m_1\) là đúng.
  • Nếu \(f(m_1) > f(m_2)\): đỉnh \(c\) phải nằm bên trái \(m_2\) (vì \(f\) đã giảm). Vậy \(c \in [l, m_2]\). Gán \(r = m_2\) là đúng.
  • Nếu \(f(m_1) = f(m_2)\): đỉnh \(c \in [m_1, m_2]\) (vì \(f\) tăng đến \(c\) rồi giảm).

Trong mọi trường hợp, đỉnh \(c\) luôn nằm trong đoạn mới. \(\blacksquare\)

Tại sao cần brute force cho số nguyên?

Khi \(r - l \leq 3\) với số nguyên, đoạn có thể chứa 4 giá trị \(\{l, l+1, l+2, l+3\}\). Nếu chỉ dùng công thức chia 3, có thể \(m_1 = m_2\) dẫn đến vòng lặp vô hạn.

Ví dụ: \([4, 5]\), \(m_1 = 4 + (5-4)/3 = 4\), \(m_2 = 5 - (5-4)/3 = 4\). Cả hai bằng 4, không thu hẹp được.

Brute force 4 phần tử đảm bảo không bỏ sót đỉnh.

Kiểm tra hàm có unimodal không

Điều kiện cần để áp dụng Ternary Search:

Kiểm tra Cách thực hiện
Hàm liên tục Đảm bảo \(f\) không có điểm gián đoạn
Đạo hàm đổi dấu đúng 1 lần \(f'(x) > 0\) rồi \(f'(x) < 0\) (hoặc ngược lại)
Không có nhiều cực trị local Số nghiệm \(f'(x) = 0\) đúng bằng 1

Nếu hàm có nhiều đỉnh, Ternary Search có thể hội tụ vào một cực trị local mà bỏ qua global optimum.

Ví dụ minh họa: Tìm MAX trên \([0, 10]\)

Cho \(f(x) = -x^2 + 6x + 5\), đỉnh tại \(x = 3\), \(f(3) = 14\).

Bước \(l\) \(r\) \(m_1\) \(m_2\) \(f(m_1)\) \(f(m_2)\) So sánh Đoạn mới
1 0 10 3.33 6.67 13.89 0.53 \(f(m_1) > f(m_2)\) \([0, 6.67]\)
2 0 6.67 2.22 4.45 13.39 11.90 \(f(m_1) > f(m_2)\) \([0, 4.45]\)
3 0 4.45 1.48 2.97 11.69 14.00 \(f(m_1) < f(m_2)\) \([1.48, 4.45]\)
4 1.48 4.45 2.47 3.46 13.62 13.85 \(f(m_1) < f(m_2)\) \([2.47, 4.45]\)

Sau mỗi bước, đoạn chứa đỉnh thu hẹp lại. Sau đủ nhiều bước, \((l + r) / 2\) hội tụ về \(x = 3\).

Đánh giá độ phức tạp

Độ phức tạp thời gian

Ternary Search trên số thực:

Mỗi bước gọi \(f\) đúng 2 lần, thu hẹp đoạn còn \(\frac{2}{3}\).

Sau \(k\) bước, độ dài đoạn: \((r - l) \cdot \left(\frac{2}{3}\right)^k\).

Để đạt độ chính xác \(\varepsilon\), cần:

\[\left(\frac{2}{3}\right)^k \cdot (r - l) \leq \varepsilon \implies k \geq \frac{\ln \frac{r - l}{\varepsilon}}{\ln \frac{3}{2}} = O\left(\log_{3/2} \frac{r - l}{\varepsilon}\right)\]

Với double precision (\(\varepsilon \approx 10^{-15}\)), \(k = 200\) là đủ.

Yếu tố Giá trị
Số lần lặp \(O(\log_{1.5}(r - l))\) cho liên tục, \(O(\log_{1.5} N)\) cho nguyên
Mỗi lần lặp \(O(T_f)\), trong đó \(T_f\) là thời gian tính \(f\)
Tổng \(O(T_f \cdot \log_{1.5} N)\)

Ternary Search trên số nguyên:

Vòng while chạy \(O(\log_{1.5} N)\) lần, mỗi lần \(O(T_f)\). Brute force đoạn cuối \(O(1)\) (tối đa 4 phần tử).

Tổng: \(O(T_f \cdot \log_{1.5} N)\).

Ternary Search 2D:

Vòng ngoài \(O(\log_{1.5} R_x)\) lần, mỗi lần gọi vòng trong \(O(\log_{1.5} R_y)\) lần, mỗi lần gọi \(f\).

Tổng: \(O(T_f \cdot \log_{1.5} R_x \cdot \log_{1.5} R_y)\).

Thuật toán Số lần lặp Gọi \(f\) mỗi bước Tổng gọi \(f\)
Binary Search \(\log_2 N\) 1 \(\log_2 N\)
Ternary Search \(\log_{1.5} N \approx 1.585 \cdot \log_2 N\) 2 \(\approx 3.17 \cdot \log_2 N\)

Ternary Search gọi \(f\) nhiều hơn gấp ~3 lần so với Binary Search. Tuy nhiên, khi \(T_f = O(1)\), cả hai đều rất nhanh.

Độ phức tạp không gian

\(O(1)\) - chỉ sử dụng các biến l, r, m1, m2.

Tình huống Khuyến nghị
Hàm monotonic Dùng Binary Search
Hàm unimodal, \(T_f = O(1)\) Dùng Ternary Search
Hàm unimodal, \(T_f\) lớn Cân nhắc Golden Section Search (gọi \(f\) 1 lần/bước)
Hàm không xác định tính chất Không dùng được Ternary Search

Các lỗi thường gặp

Nhầm unimodal với monotonic

Hàm monotonic (ví dụ \(f(x) = 2x + 3\)) luôn tăng hoặc luôn giảm. Dùng Binary Search, không phải Ternary Search.

Hàm unimodal (ví dụ \(f(x) = -x^2 + 4x\)) tăng rồi giảm. Dùng Ternary Search.

Integer overflow khi tính \(m_1\), \(m_2\)

1
2
3
4
5
6
// SAI: (r - l) có thể tràn nếu l, r là long long
long long m1 = l + (r - l) / 3;

// ĐÚNG: dùng hằng số đúng kiểu
long long m1 = l + (r - l) / 3LL;
long long m2 = r - (r - l) / 3LL;

Dừng quá sớm với floating point

1
2
3
4
5
// SAI: so sánh với epsilon có thể không dừng
while (r - l > 1e-9) { ... }

// ĐÚNG: lặp số lần cố định
for (int iter = 0; iter < 200; iter++) { ... }

Với double (15-16 chữ số thập phân), 200 lần lặp đủ vì \((2/3)^{200} \approx 10^{-35}\).

Quên brute force với số nguyên

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// SAI: không brute force khi r - l <= 3
while (r - l > 3) {
    // ternary search
}
// Có thể bỏ sót!

// ĐÚNG: brute force đoạn còn lại
while (r - l > 3) {
    // ternary search
}
int best = l;
for (int i = l + 1; i <= r; i++) {
    if (f(i) > f(best)) best = i;
}

Hàm không thực sự unimodal

Nếu hàm có nhiều đỉnh, Ternary Search có thể hội tụ vào cực trị local mà bỏ qua global optimum. Phải kiểm tra tính unimodal trước khi áp dụng.

Bài tập luyện tập

Mã bài Tên bài tập Độ khó Kiểu bài tập (Bản chất) Bài học lý thuyết
ts-find-max Tìm max ⭐ Ternary Search - Tìm max cơ bản Ternary Search
ts-parabola Parabol ⭐⭐ Ternary Search - Hàm bậc 2 Ternary Search
ts-peak Đỉnh núi ⭐⭐ Ternary Search - Mảng tăng/giảm Ternary Search
ts-distance Khoảng cách ⭐⭐⭐ Ternary Search - Tổng khoảng cách Ternary Search
ts-cover Phủ sóng ⭐⭐⭐ Ternary Search - Bán kính tối thiểu Ternary Search
ts-delivery Giao hàng ⭐⭐⭐ Ternary Search - Vị trí tối ưu Ternary Search
ts-angle Góc tối ưu ⭐⭐⭐ Ternary Search - Góc bắn Ternary Search
ts-circle Hình tròn ⭐⭐⭐⭐ Ternary Search - Hình tròn nhỏ nhất Ternary Search
ts-convex Hàm lồi ⭐⭐⭐⭐ Ternary Search - Hàm lồi Ternary Search

Tài liệu tham khảo

Bài viết này là một phần của FPTOJ Wiki - Dự án xây dựng kho tài liệu lập trình thi đấu tiếng Việt.

💬 Bình luận