Binary Search

Tìm trong dãy đã sắp

Bài toán: cho $a_1 \le a_2 \le \dots \le a_n$ và số $x$, tìm vị trí đầu tiên có $a_i \ge x$. Câu hỏi này luôn có đáp án, dù $x$ vắng mặt hay lặp lại nhiều lần (nếu không có vị trí nào thì quy ước đáp án là $n + 1$), và từ nó đọc ra mọi thứ khác: $x$ có mặt khi vị trí đó $\le n$ và giá trị ở đó bằng $x$.

Xét vị trí giữa $mid$. Nếu $a_{mid} \ge x$ thì $mid$ là một ứng viên, và vị trí đầu tiên cần tìm không nằm sau $mid$. Nếu $a_{mid} < x$ thì mọi vị trí từ $mid$ trở về trước đều nhỏ hơn $x$ vì dãy tăng. Mỗi lần so sánh loại được ít nhất một nửa đoạn còn nghi ngờ.

ll l = 1, r = n, res = n + 1;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (a[mid] >= x) r = (res = mid) - 1;
    else l = mid + 1;
}

Vì sao đúng. Đoạn $[l, r]$ là các vị trí chưa biết. Mọi vị trí trước $l$ đã biết là $a_i < x$, mọi vị trí sau $r$ đã biết là $a_i \ge x$. Biến res luôn bằng $r + 1$: lúc đầu $res = n + 1 = r + 1$, mỗi lần r = (res = mid) - 1 lại gán cả hai cùng lúc, còn nhánh l = mid + 1 không đụng tới $r$. Vì $mid$ luôn nằm trong $[l, r]$ nên đoạn chưa biết co lại ít nhất một ô mỗi vòng, và vòng lặp dừng khi $l = r + 1$: không còn vị trí nào chưa biết, mọi vị trí trước $res$ có $a_i < x$, mọi vị trí từ $res$ trở đi có $a_i \ge x$. Vậy $res$ đúng là vị trí đầu tiên cần tìm, kể cả khi bằng $n + 1$.

Với $a = (2, 5, 8, 12, 16, 23, 38, 56, 72, 91)$ và $x = 23$: $mid = 5$, $a_5 = 16 < 23$ nên $l = 6$; $mid = 8$, $56 \ge 23$ nên $res = 8$, $r = 7$; $mid = 6$, $23 \ge 23$ nên $res = 6$, $r = 5$. Dừng: vị trí đầu tiên có $a_i \ge 23$ là 6.

Mỗi vòng đoạn $[l, r]$ còn không quá một nửa, nên sau tối đa $\lceil \log_2 (n+1) \rceil$ vòng là xong: 18 vòng với $n = 2 \cdot 10^5$, 60 vòng với miền cỡ $10^{18}$. Ba chỗ hay sai, và đều tránh được nếu giữ đúng khuôn:

• Lặp vô hạn. Viết while (l < r) rồi nhánh l = mid thì khi $r = l + 1$ ta có $mid = l$, $l$ không nhúc nhích và vòng lặp không bao giờ dừng. Khuôn trên luôn bỏ $mid$ ra khỏi đoạn chưa biết (mid - 1 hoặc mid + 1) nên không rơi vào chuyện đó.
• Tràn số. (l + r) >> 1 dịch tổng sang phải một bit, tức chia đôi rồi bỏ phần lẻ, như (l + r) / 2 với số không âm. Nó an toàn với long long khi hai đầu không vượt cỡ $4 \cdot 10^{18}$. Với int, tổng hai số cỡ $10^9$ đã tràn.
• Điều kiện không đơn điệu. Chương trình vẫn dừng và vẫn in ra một số, nhưng số đó vô nghĩa. Trước khi viết code, hãy nói được vì sao nếu $x$ thỏa thì $x + 1$ (hay $x - 1$) cũng thỏa.

Ví dụĐếm Không Vượt Ngưỡng

Đề. Mảng $a$ gồm $n \le 2 \cdot 10^5$ số, $m \le 2 \cdot 10^5$ truy vấn $b_j$. Với mỗi $b_j$ đếm số phần tử $a_i \le b_j$.

Lời giải. Sắp $a$ một lần. Số phần tử không vượt $b$ chính là vị trí đầu tiên có $a_i > b$, trừ 1: mọi phần tử trước vị trí đó đều $\le b$. Tìm vị trí đó bằng khuôn trên với điều kiện a[mid] > b. Cả bài $O((n + m) \log n)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll n, m, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (ll j = 1; j <= m; j++) {
        ll b;
        cin >> b;
        ll l = 1, r = n, res = n + 1;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (a[mid] > b) r = (res = mid) - 1;
            else l = mid + 1;
        }
        cout << res - 1 << " \n"[j == m];
    }
}

Input6 4
-2 5 5 0 9 1
-3 0 5 10

Output0 2 5 6

Khuôn tổng quát: tìm ranh giới của một điều kiện

Chương trình ở mục trước chỉ chạm vào mảng ở một biểu thức, a[mid] >= x. Thay nó bằng một điều kiện $P(x)$ bất kỳ đơn điệu, tức nếu $P(x)$ đúng thì $P(y)$ đúng với mọi $y > x$, thì cùng vòng lặp ấy tìm ra giá trị nhỏ nhất mà $P$ đúng. Dãy giá trị của $P$ có dạng sai, …, sai, đúng, …, đúng, và ta đi tìm ranh giới. Trong code, $P$ là một hàm check.

ll l = lo, r = hi, res = -1;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (check(mid)) r = (res = mid) - 1;
    else l = mid + 1;
}

Nhiều bài hỏi giá trị lớn nhất thỏa điều kiện; khi đó điều kiện đúng ở bên trái và sai ở bên phải. Chỉ cần đổi hướng: thỏa thì ghi nhận rồi tìm tiếp bên phải.

if (check(mid)) l = (res = mid) + 1;
else r = mid - 1;

Chứng minh y hệt mục trước. res = -1 (hay một giá trị nằm ngoài miền) cho biết không có giá trị nào thỏa, ta kiểm bằng một phép so sánh, không cần nhánh xử lý riêng.

Ví dụ gọn nhất là tính $\lfloor \sqrt n \rfloor$ với $n \le 10^{18}$ mà không dùng số thực. Điều kiện $x^2 \le n$ đúng với $x$ nhỏ, sai với $x$ lớn; đáp án là giá trị lớn nhất còn đúng. Miền tìm là $[0, 10^9]$, và $mid^2 \le 10^{18}$ vẫn nằm trong long long.

ll l = 0, r = 1e9, res = 0;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (mid * mid <= n) l = (res = mid) + 1;
    else r = mid - 1;
}

Dạng “phần tử thứ $k$” cũng đi qua khuôn này. Nếu đếm nhanh được $\mathrm{cnt}(x)$ là số phần tử không vượt $x$, thì phần tử thứ $k$ là giá trị nhỏ nhất có $\mathrm{cnt}(x) \ge k$, kể cả khi ta không liệt kê nổi các phần tử. $\mathrm{cnt}$ không giảm theo $x$ nên điều kiện đơn điệu.

Ví dụPhần Tử Thứ K Ngoài Các Bội

Đề. Xét dãy tăng các số nguyên dương không chia hết cho $n$ ($n \le 10^9$). Tìm phần tử thứ $k$ ($k \le 10^9$). $t \le 1000$ test.

Lời giải. Trong $1..x$ có $\lfloor x/n \rfloor$ bội của $n$, nên $\mathrm{cnt}(x) = x - \lfloor x/n \rfloor$ số không chia hết. Đáp án là $x$ nhỏ nhất có $\mathrm{cnt}(x) \ge k$. Vì $n \ge 2$, cứ hai số liên tiếp có ít nhất một số không chia hết cho $n$, nên $\mathrm{cnt}(2k) \ge k$ và miền tìm $[1, 2k]$ chắc chắn chứa đáp án. Mỗi test khoảng 31 vòng.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t, n, k;

signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> k;
        ll l = 1, r = 2 * k, res = 2 * k;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (mid - mid / n >= k) r = (res = mid) - 1;
            else l = mid + 1;
        }
        cout << res << '\n';
    }
}

Input4
4 8
2 6
5 1
100 105

Output10
11
1
106

lower_bound và upper_bound

Hai hàm của STL là chặt nhị phân trên mảng đã sắp, đóng gói sẵn. Với dãy tăng và số $x$:

• lower_bound trả vị trí đầu tiên có $a_i \ge x$, đúng kết quả của mục đầu;
• upper_bound trả vị trí đầu tiên có $a_i > x$.

Cả hai trả end khi không có vị trí nào. Đọc theo nghĩa đếm dễ nhớ hơn: với mảng $a_1..a_n$, lower_bound(a + 1, a + n + 1, x) - a - 1 bằng số phần tử nhỏ hơn $x$, còn upper_bound trừ tương tự bằng số phần tử không lớn hơn $x$. Hiệu hai hàm là số phần tử bằng $x$.

Gọi lb là vị trí lower_bound (đánh số từ 1), các câu hỏi thường gặp đọc thẳng ra: $x$ có mặt khi lb <= n && a[lb] == x; phần tử nhỏ nhất không nhỏ hơn $x$ là a[lb]; phần tử gần $x$ nhất là một trong hai a[lb - 1] và a[lb], vì mọi phần tử trước a[lb - 1] và sau a[lb] đều xa $x$ hơn.

Ba điều cần nhớ khi dùng. Dãy phải được sắp đúng thứ tự mà hàm dùng; sắp giảm dần rồi gọi lower_bound mặc định thì kết quả sai mà không báo lỗi. Với set và map, gọi hàm thành viên s.lower_bound(x), tốn $O(\log n)$; hàm tự do lower_bound(s.begin(), s.end(), x) vẫn đúng nhưng đi từng nút và tốn $O(n)$. Và khi cần điều kiện khác “nhỏ hơn $x$”, viết khuôn ở mục trước còn nhanh hơn đi tìm hàm thư viện.

Ví dụChi Phí Đưa Về Cùng Mốc

Đề. Dãy $n$ số, $q$ truy vấn $x$ (độc lập), mỗi truy vấn hỏi tổng $|a_1 - x| + |a_2 - x| + \dots + |a_n - x|$. $n, q \le 2 \cdot 10^5$, $0 \le a_i, x \le 10^9$.

Lời giải. Dấu giá trị tuyệt đối tách theo một điều kiện: phần tử nhỏ hơn $x$ góp $x - a_i$, phần tử không nhỏ hơn $x$ góp $a_i - x$. Nếu $a$ đã sắp thì nhóm “nhỏ hơn $x$” là $k$ phần tử đầu, với $k$ tìm bằng lower_bound, và tổng mỗi nhóm lấy bằng tổng tiền tố (bài 02):

Mỗi truy vấn $O(\log n)$; duyệt cả dãy cho từng truy vấn tốn $nq = 4 \cdot 10^{10}$. Tích $k \cdot x$ tới $2 \cdot 10^{14}$, dùng long long.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll n, q, a[N], pre[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (ll i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    while (q--) {
        ll x;
        cin >> x;
        ll k = lower_bound(a + 1, a + n + 1, x) - a - 1;
        cout << k * x - pre[k] + (pre[n] - pre[k]) - (n - k) * x << '\n';
    }
}

Input3 3
1 4 8
0
5
10

Output13
8
17

Chặt nhị phân trên đáp án

Nhiều bài không có mảng nào để tìm, nhưng đáp án là một số nguyên trong miền rất lớn, và có một câu hỏi rẻ hơn câu hỏi gốc: “giá trị $x$ đã đủ chưa?”. Nếu câu hỏi đó đơn điệu theo $x$ thì đáp án là ranh giới của nó.

Bài toán thử: $n$ sợi dây dài $\ell_i$, cắt mỗi sợi thành các đoạn nguyên dài đúng $x$, phần thừa bỏ đi, cần ít nhất $k$ đoạn; tìm $x$ lớn nhất. Thử từng $x$ tốn $10^9 \cdot n$ phép. Nhưng nếu độ dài $x$ cắt đủ $k$ đoạn thì mọi $x' < x$ cũng đủ, vì $\lfloor \ell_i / x' \rfloor \ge \lfloor \ell_i / x \rfloor$: điều kiện đúng ở bên trái, sai ở bên phải, đúng dạng “giá trị lớn nhất”.

Mọi bài kiểu này đi qua bốn câu hỏi, trả lời chúng trước khi gõ code:

1. Đáp án là gì, nằm trong miền nào? Câu trả lời cho hai đầu l, r và giá trị ban đầu của res (trường hợp vô nghiệm).
2. Hàm check(x) là gì, tốn bao lâu? Thường là một lượt duyệt $O(n)$, đôi khi kèm tham lam.
3. Vì sao check đơn điệu? Một câu dạng “nếu $x$ làm được thì $x - 1$ cũng làm được, vì…”.
4. Hàm kiểm tra có tràn số không? Tổng chi phí là $\lceil \log_2 L \rceil \cdot O(\text{check})$; đặt miền rộng gần như miễn phí vì độ dài miền chỉ nằm trong logarit, nhưng giá trị $x$ lớn có thể làm tổng trong check vượt long long. Cách chữa quen thuộc là dừng ngay khi tổng đã đủ mức cần.

Vài dạng lặp lại để nhận ra khi đọc đề. Tối thiểu hóa giá trị lớn nhất: “chia dãy thành $k$ đoạn sao cho tổng đoạn lớn nhất nhỏ nhất”; hỏi ngược có làm được với mọi phần không vượt $M$ không, điều kiện đúng từ một $M$ nào đó trở lên. Tối đa hóa giá trị nhỏ nhất: “đặt $c$ trạm sao cho khoảng cách nhỏ nhất lớn nhất”; hỏi có làm được với mọi khoảng cách không nhỏ hơn $D$ không. Hàm kiểm tra của cả hai thường là một lượt tham lam (bài 04).

Ví dụChia Dãy Cân Bằng

Đề. Dãy $n \le 2 \cdot 10^5$ số nguyên dương $a_i \le 10^9$, chia thành đúng $k$ đoạn liên tiếp không rỗng; giá của cách chia là tổng lớn nhất trong các đoạn. Tìm giá nhỏ nhất.

Lời giải. Dạng tối thiểu hóa giá trị lớn nhất. Gọi $P(M)$ là “chia được thành $k$ đoạn mà đoạn nào cũng có tổng không vượt $M$”; $P(M)$ đúng thì $P(M + 1)$ đúng, nên tìm $M$ nhỏ nhất thỏa.

Kiểm $P(M)$ bằng tham lam: quét từ trái, cộng phần tử vào đoạn hiện tại, khi cộng thêm sẽ vượt $M$ thì mở đoạn mới. Tham lam dùng ít đoạn nhất có thể, vì sau $j$ đoạn nó luôn phủ được ít nhất bằng $j$ đoạn đầu của bất kỳ cách chia hợp lệ nào (các số dương nên đoạn nào kéo dài thêm cũng chỉ tốn hơn). Nếu nó dùng ít hơn $k$ đoạn thì tách bớt đoạn dài là đủ $k$ đoạn, tổng không tăng. Vậy $P(M)$ đúng khi và chỉ khi tham lam dùng không quá $k$ đoạn, với điều kiện $M$ không nhỏ hơn phần tử lớn nhất.

Miền tìm là từ phần tử lớn nhất tới tổng mọi phần tử, tối đa 48 lần kiểm, mỗi lần $O(n)$: cỡ $10^7$ phép tính. Tổng tới $2 \cdot 10^{14}$ nên dùng long long.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll n, k, a[N];

bool check(ll M) {
    ll parts = 1, cur = 0;
    for (ll i = 1; i <= n; i++) {
        if (cur + a[i] > M) {
            parts++;
            cur = a[i];
        } else cur += a[i];
    }
    return parts <= k;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    ll mx = 0, sum = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
        sum += a[i];
    }
    ll l = mx, r = sum, res = sum;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }
    cout << res << '\n';
}

Input7 3
4 2 7 3 5 1 6

Output12

Trên ví dụ: thử $M = 17$ được hai đoạn, đúng; $M = 11$ cần bốn đoạn $(4\,2)(7\,3)(5\,1)(6)$, sai; $M = 14$ được ba đoạn, đúng; $M = 12$ được $(4\,2)(7\,3)(5\,1\,6)$, đúng. Đáp án 12.

Chặt nhị phân trên số thực

Khi đáp án là số thực, không còn “hai số nguyên liền nhau” để làm điều kiện dừng. Vòng lặp vẫn là chia đôi miền, nhưng ta chạy một số vòng cố định:

double l = 0, r = 1e9;
for (ll it = 1; it <= 100; it++) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

Sau $t$ vòng, độ dài miền còn $(r_0 - l_0) / 2^t$. Với miền cỡ $10^9$ và $t = 100$, đó là khoảng $8 \cdot 10^{-22}$, nhỏ hơn mọi chênh lệch mà double phân biệt được; các vòng thừa vô hại vì khi hai đầu đã sát nhau, mid trùng một đầu và phép gán không đổi gì. Nếu check nặng thì 50 vòng đã đủ cho sai số $10^{-6}$ trên miền $10^9$.

Lý do ta không viết while (r - l > 1e-9): double chỉ giữ được khoảng 16 chữ số có nghĩa, nên ở cỡ $10^8$ hai số liền nhau cách nhau khoảng $1{,}5 \cdot 10^{-8}$. Tới lúc l và r liền nhau, r - l kẹt ở khoảng cách đó và vòng lặp không dừng.

Chặt nhị phân chỉ tìm ranh giới của điều kiện đơn điệu. Hàm có một đỉnh (tăng rồi giảm) thì cần chặt tam phân, bài 57.

Ví dụChia Bánh Tròn

Đề. $N \le 10^4$ bánh tròn bán kính $r_i \le 10^4$, chia cho $F + 1$ người, mỗi người một miếng cùng diện tích $S$, mỗi miếng nằm trọn trong một bánh, phần thừa bỏ đi. Tìm $S$ lớn nhất, sai số $10^{-3}$.

Lời giải. Bánh diện tích $A_i = \pi r_i^2$ cho $\lfloor A_i / S \rfloor$ miếng; tổng số miếng không tăng khi $S$ tăng, nên điều kiện “đủ $F + 1$ miếng” đúng với $S$ nhỏ, sai với $S$ lớn. Miền là từ 0 tới diện tích bánh lớn nhất. Mỗi lần kiểm $O(N)$, dừng sớm khi đã đủ người; 100 vòng mỗi test. Dùng acos(-1) cho $\pi$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t, n, f;
double area[10005];

bool check(double s) {
    ll cnt = 0;
    for (ll i = 1; i <= n; i++) {
        cnt += (ll)(area[i] / s);
        if (cnt >= f + 1) return true;
    }
    return false;
}

signed main() {
    cin >> t;
    double pi = acos(-1);
    while (t--) {
        cin >> n >> f;
        double l = 0, r = 0;
        for (ll i = 1; i <= n; i++) {
            ll x;
            cin >> x;
            area[i] = pi * x * x;
            r = max(r, area[i]);
        }
        for (ll it = 1; it <= 100; it++) {
            double mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("%.4f\n", l);
    }
}

Input2
3 3
4 4 4
2 1
1 2

Output25.1327
6.2832