Ternary Search

Tìm kiếm tam phân (ternary search) tìm điểm cực trị (cực tiểu hoặc cực đại) của một hàm đơn cực (unimodal) trên đoạn $[lo,hi]$ trong $O(\log N)$ truy vấn giá trị hàm — thay vì duyệt toàn bộ $O(N)$ điểm. Nó là người anh em của tìm kiếm nhị phân: binary search tìm ngưỡng trên hàm đơn điệu, còn ternary search tìm đỉnh/đáy trên hàm "tăng rồi giảm" (hoặc "giảm rồi tăng").

Điều kiện áp dụng (BẮT BUỘC): hàm $f$ phải đơn cực trên $[lo,hi]$:

• Để tìm cực tiểu: $f$ phải giảm nghiêm ngặt rồi tăng nghiêm ngặt (hình chữ V / hàm lồi). Có đúng một đáy.
• Để tìm cực đại: $f$ phải tăng nghiêm ngặt rồi giảm nghiêm ngặt (hình chữ Λ / hàm lõm). Có đúng một đỉnh.

Nếu hàm có đoạn phẳng (hai điểm liền kề bằng nhau) hoặc nhiều cực trị, ternary search có thể trả về sai — đây là cái bẫy lớn nhất, sẽ nói kỹ ở mục Lỗi thường gặp.

Ý tưởng / Trực giác

Lấy ví dụ tìm cực tiểu của hàm lồi. Mỗi bước ta chia đoạn $[lo,hi]$ thành ba phần bằng hai điểm:

$$m_1=lo+\frac{hi-lo}{3},m_2=hi-\frac{hi-lo}{3}$$

với $m_1<m_2$. So sánh $f(m_1)$ và $f(m_2)$ cho phép loại bỏ một phần ba đoạn:

• Nếu $f(m_1)<f(m_2)$: đáy không thể nằm bên phải $m_2$. Vì sao? Hàm lồi giảm rồi tăng. Nếu đáy nằm trong $(m_2,hi]$ thì cả $m_1,m_2$ đều ở nhánh giảm, suy ra $f(m_1)>f(m_2)$ — mâu thuẫn. Vậy đáy nằm trong $[lo,m_2]$, ta gán $hi=m_2$.
• Nếu $f(m_1)>f(m_2)$: đối xứng, đáy nằm trong $[m_1,hi]$, ta gán $lo=m_1$.
• Nếu $f(m_1)=f(m_2)$: do tính đơn cực nghiêm ngặt, đáy nằm strictly giữa $m_1$ và $m_2$, nên thu hẹp về $[m_1,m_2]$ đều an toàn.

Điểm cốt lõi: mỗi lần so sánh cắt bỏ $1/3$ độ dài đoạn một cách an toàn, nên đoạn co lại theo cấp số nhân với hệ số $2/3$. Sau $k$ bước, độ dài còn $(2/3{)}^k$ lần ban đầu — đó chính là nguồn gốc của $O(\log N)$. Khác với binary search dùng dấu của một điểm, ternary search cần hai điểm vì chỉ một giá trị $f(m)$ không cho biết ta đang ở nhánh trái hay nhánh phải của đáy; phải so sánh hai điểm mới biết hướng dốc.

Ví dụ chạy tay

Tìm cực tiểu nguyên của $f(x)=(x-7{)}^2+3$ trên $[0,12]$ (đáy thật ở $x=7$, $f(7)=3$). Bảng giá trị:

x   :  0   1   2   3   4   5   6   7   8   9  10  11  12
f(x): 52  39  28  19  12   7   4   3   4   7  12  19  28
                                ^đáy thật

Quy ước: L = lo, R = hi, a = m1, b = m2, vùng bị loại bôi x.

Bước 1: $lo=0,hi=12$ → $m_1=0+12/3=4$, $m_2=12-12/3=8$. $f(4)=12<f(8)=4$? Không, $12>4$ nên đáy ở phải: $lo=m_1=4$.

x   :  0   1   2   3   4   5   6   7   8   9  10  11  12
       x   x   x   x   L       a?      R
f(4)=12  >  f(8)=4  -> bo trai, lo=4

Bước 2: $lo=4,hi=12$ → khoảng dài 8, $m_1=4+8/3=6$, $m_2=12-8/3=9$ (chia nguyên). $f(6)=4<f(9)=7$ → đáy ở trái: $hi=m_2=9$.

x   :              4   5   6   7   8   9  10  11  12
                   L       a       b   R   x   x   x
f(6)=4  <  f(9)=7  -> bo phai, hi=9

Bước 3: $lo=4,hi=9$, độ dài $5>2$ → $m_1=4+5/3=5$, $m_2=9-5/3=8$. $f(5)=7<f(8)=4$? Không → $lo=5$.

x   :              4   5   6   7   8   9
                   x   L   a?      b   R
f(5)=7  >  f(8)=4  -> lo=5

Bước 4: $lo=5,hi=9$, độ dài $4>2$ → $m_1=5+4/3=6$, $m_2=9-4/3=7$. $f(6)=4>f(7)=3$ → $lo=6$. Giờ $hi-lo=9-6=3>2$, tiếp. Bước 5: $lo=6,hi=9$ → $m_1=6+1=7$, $m_2=9-1=8$. $f(7)=3<f(8)=4$ → $hi=8$. Còn $[6,8]$, độ dài $2$, dừng vòng lặp.

Quét nốt $x\in \{6,7,8\}$: $f(6)=4,f(7)=3,f(8)=4$ → nhỏ nhất tại $x=7$, $f=3$. Đúng.

Cài đặt

Trên số thực (lặp cố định số vòng)

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

// Tìm x trong [lo, hi] TỐI THIỂU HÓA f (hàm lồi, giảm rồi tăng)
double ternary_min_real(double lo, double hi, function<double(double)> f) {
    // Mỗi vòng đoạn co lại theo hệ số 2/3; ~200 vòng -> sai số ~ (2/3)^200
    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;   // đáy không ở bên phải m2
        else               lo = m1;   // đáy không ở bên trái m1
    }
    return (lo + hi) / 2;             // trả về điểm giữa đoạn cuối
}

// Tìm CỰC ĐẠI (hàm lõm): chỉ đổi chiều so sánh
double ternary_max_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;
}

Dùng số vòng cố định thay vì điều kiện while (hi - lo > eps) để tránh vòng lặp vô tận do sai số dấu phẩy động. Với $200$ vòng, sai số $\approx (2/3{)}^{200}·(hi-lo)\approx {10}^{-35}·(hi-lo)$ — thừa cho mọi yêu cầu ${10}^{-9}$ (chỉ cần ~$100$ vòng).

Trên số nguyên (thu hẹp tới khi còn ≤ 3 điểm rồi quét tay)

// Tìm x NGUYÊN trong [lo, hi] tối thiểu hóa f (đơn cực nghiêm ngặt)
long long ternary_min_int(long long lo, long long hi, function<long long(long long)> f) {
    while (hi - lo > 2) {                 // còn > 3 điểm thì tiếp tục
        long long m1 = lo + (hi - lo) / 3;
        long long m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) hi = m2;
        else               lo = m1;
    }
    long long best = lo;                  // quét nốt các điểm còn lại [lo..hi]
    for (long long x = lo; x <= hi; x++)
        if (f(x) < f(best)) best = x;
    return best;                          // trả về vị trí cực tiểu
}

Với số nguyên, không lặp tới hi == lo vì khi $hi-lo$ nhỏ, công thức chia nguyên có thể khiến $m_1$ hoặc $m_2$ trùng biên và vòng lặp không tiến (kẹt vô hạn). An toàn nhất là dừng khi còn $\le 3$ điểm rồi so sánh trực tiếp.

Độ phức tạp

• Thời gian: $O({\log }_{3/2}L·C)$, trong đó $L$ là độ dài miền tìm kiếm (số nguyên) hoặc tỉ lệ $\frac{hi-lo}{\epsilon }$ (số thực), còn $C$ là chi phí một lần tính $f$. Mỗi vòng đoạn co theo hệ số $2/3$ nên số vòng để đạt độ rộng $\le 1$ (hoặc $\le \epsilon$) là ${\log }_{3/2}L=O(\log L)$. Lưu ý: mỗi vòng tính $f$ hai lần — hằng số gấp đôi binary search, nhưng vẫn cùng bậc logarit. Nếu $f$ tốn $O(N)$ (vd cộng khoảng cách tới $N$ điểm), tổng là $O(N\log L)$.
• Bộ nhớ: $O(1)$ ngoài dữ liệu đầu vào — chỉ giữ vài biến lo, hi, m1, m2. Bản đệ quy sẽ tốn $O(\log L)$ stack, nên ưu tiên vòng lặp.

⚠️ Lỗi thường gặp

• Hàm không thực sự đơn cực: đây là lỗi nghiêm trọng nhất. Nếu $f$ có nhiều cực trị, hoặc tăng/giảm không nghiêm ngặt, kết quả sai mà không báo lỗi. Hãy chứng minh tính đơn cực trước khi dùng (vd tổng các hàm lồi vẫn lồi; khoảng cách Euclid từ điểm cố định tới điểm chạy trên đoạn thẳng là hàm lồi). Khi nghi ngờ, kiểm thử bằng brute force trên dữ liệu nhỏ.
• Đoạn phẳng làm so sánh < quyết định sai hướng: nếu tồn tại $m_1\ne m_2$ mà $f(m_1)=f(m_2)$ do hàm có "mặt bàn" phẳng, nhánh else (gán lo = m1) có thể vứt bỏ luôn đáy thật. Với số nguyên có đoạn bằng nhau, hãy thu hẹp tới khoảng nhỏ rồi quét tuyến tính thay vì tin tưởng tuyệt đối vào so sánh.
• Tràn số khi tính $m_1,m_2$ hoặc giá trị $f$: với miền số nguyên lớn (vd $\pm {10}^9$), lo + (hi - lo)/3 an toàn hơn (lo + 2*hi)/3 (vế sau dễ tràn int). Giá trị hàm như $(x-c{)}^2$ hay tổng khoảng cách dễ vượt int — khai báo $f$ trả long long.
• Vòng lặp vô hạn trên số nguyên: điều kiện while (lo < hi) với chia nguyên có thể khiến $m_1=lo$, $m_2=hi$ và đoạn không co. Luôn dừng khi hi - lo <= 2 rồi xử lý nốt bằng tay.
• Dùng while (hi - lo > eps) cho số thực: với hàm gần phẳng quanh đáy, sai số dấu phẩy động khiến điều kiện không bao giờ thoả → treo. Dùng số vòng cố định (100–200) thay cho ngưỡng eps.
• Nhầm chiều min/max: tìm cực đại nhưng để nguyên dấu so sánh của bản tìm cực tiểu (hoặc ngược lại) sẽ cho kết quả ở đầu mút sai. Quy tắc: tìm min dùng if (f(m1) < f(m2)) hi = m2;, tìm max chỉ việc đổi < thành >.

Biến thể / Mở rộng

• Bậc hai (golden-section search): thay vì chia ba đều, dùng tỉ lệ vàng $\phi$ để tái sử dụng một điểm đánh giá ở vòng sau, giảm số lần gọi $f$ từ $2$ xuống $1$ mỗi vòng — hữu ích khi $f$ rất đắt.
• Tối ưu trên dãy đơn cực rời rạc: mảng "tăng rồi giảm" (mountain array), tìm đỉnh; hoặc khoảng cách từ điểm $P$ tới các đỉnh của bao lồi (convex hull) là đơn cực theo chỉ số đỉnh, cho phép tìm đỉnh xa/gần nhất trong $O(\log N)$.
• Quy về binary search trên đạo hàm: nếu $f$ khả vi và $f^{\prime }$ đơn điệu, tìm nghiệm $f^{\prime }(x)=0$ bằng binary search cũng cho cực trị, đôi khi ổn định hơn về số học.
• Ternary search lồng nhau (2D): tối ưu hàm lồi hai biến $f(x,y)$ bằng cách ternary search theo $x$, mỗi lần lại ternary search theo $y$ để tính ${min}_{y}f(x,y)$ — tổng $O({\log }^2)$ truy vấn, áp dụng khi hàm lồi theo từng biến.

So sánh nhanh với tìm kiếm nhị phân:

Bài tập luyện

• Cực đại hóa (maximize) (Nâng cao) Với mỗi truy vấn, giá trị cần tối đa là hàm unimodal theo số phần tử $k$ lấy từ đầu dãy đã sắp; chặt tam phân trên số nguyên $k$ là cách giải trực tiếp nhất.
• Balancing the Barns (balbarns) (Kỳ cựu) Kết hợp hai lớp: chặt nhị phân đáp án bên ngoài, bên trong chặt tam phân trên $m$ để cực tiểu một tổng các hàm $max$ tuyến tính (hàm lồi); chú ý các đoạn bằng nhau khi chặt trên số nguyên.
• Yếu và Nghèo (weakpoor) (Kỳ cựu) Dạng kinh điển: độ yếu của dãy sau khi trừ $x$ là hàm lồi theo $x$, chặt tam phân trên số thực khoảng 100 vòng, mỗi lần đánh giá bằng Kadane $O(n)$.
• Giấc mơ freelancer (freedream) (Chuyên gia) Cực đại một hàm lõm (min của các hàm tuyến tính) trên đoạn số thực; cần tự chứng minh tính lõm trước khi chặt tam phân.