Thuật Toán Tìm Kiếm Nhị Phân

1. Khái niệm & bản chất của tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân (Binary Search) là thuật toán tìm kiếm dựa trên nguyên lý chia để trị (Divide and Conquer). Bằng cách so sánh giá trị cần tìm với phần tử ở chính giữa không gian tìm kiếm, thuật toán loại bỏ chính xác một nửa không gian tìm kiếm sau mỗi bước lặp.

1.1. Điều kiện tiên quyết (prerequisite condition)

Thuật toán tìm kiếm nhị phân CHỈ HOẠT ĐỘNG ĐƯỢC khi không gian tìm kiếm hoặc mảng dữ liệu có tính chất đơn điệu (Monotonicity):

• Mảng đã được sắp xếp tăng dần hoặc giảm dần.
• Hoặc một hàm mệnh đề logic $f(x) \in \{\text{True}, \text{False}\}$ thỏa mãn: nếu $f(x_0) = \text{True}$ thì $\forall x \ge x_0, f(x) = \text{True}$ (hoặc ngược lại).

1.2. Phân tích độ phức tạp thời gian $\mathcal{O}(\log N)$

Giả sử không gian tìm kiếm ban đầu có kích thước $N$:

• Bước 1: Thu hẹp còn $\frac{N}{2}$.
• Bước 2: Thu hẹp còn $\frac{N}{4} = \frac{N}{2^2}$.
• Bước $k$: Thu hẹp còn $\frac{N}{2^k}$.

Quá trình dừng lại khi kích thước không gian tìm kiếm bằng $1 \implies \frac{N}{2^k} = 1 \iff 2^k = N \iff k = \log_2 N$.

• Với $N = 10^5 \implies \log_2(10^5) \approx 17$ lần thu hẹp không gian.
• Với $N = 10^9 \implies \log_2(10^9) \approx 30$ lần thu hẹp không gian.
• Với $N = 10^{18} \implies \log_2(10^{18}) \approx 60$ lần thu hẹp không gian.

Bản chất hiệu năng: Trên không gian nghiệm lên tới $10^{18}$, thuật toán chỉ cần khoảng $60$ lần thu hẹp không gian. Tổng thời gian thực tế của chương trình sẽ bằng:

$\text{Total Time} = \mathcal{O}\Big(\log(\text{Range}) \times \text{Complexity}(\text{check})\Big)$ Nếu hàm kiểm tra $\text{check}(mid)$ chạy trong $\mathcal{O}(N)$ với $N = 10^5$, chương trình chỉ mất khoảng $60 \times 10^5 = 6 \cdot 10^6$ phép tính (thực thi trong khoảng $0.02$ giây).

2. Tìm kiếm nhị phân trên mảng đã sắp xếp

2.1. Tìm chính xác giá trị $X$ (exact search)

Khởi tạo hai con trỏ biên: $low = 0, high = N - 1$.

• Tính trung điểm an toàn: $mid = low + \frac{high - low}{2}$.
• Nếu $A[mid] == X \implies$ Tìm thấy tại vị trí $mid$.
• Nếu $A[mid] < X \implies$ Giá trị $X$ chỉ có thể nằm ở nửa phải $\implies low = mid + 1$.
• Nếu $A[mid] > X \implies$ Giá trị $X$ chỉ có thể nằm ở nửa trái $\implies high = mid - 1$.

Ví dụ minh họa 1: Tìm kiếm giá trị $X = 23$

Cho mảng đã sắp xếp gồm 10 phần tử: $A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]$

Bảng mô phỏng từng bước thu hẹp không gian tìm kiếm:

2.2. Tìm kiếm phần tử biên: lower_bound và upper_bound

Trong lập trình thi đấu, dạng toán tìm vị trí biên quan trọng hơn nhiều so với tìm chính xác:

1. lower_bound (Tìm phần tử nhỏ nhất $\ge X$): * Tìm vị trí đầu tiên mà giá trị tại đó $\ge X$. * Nếu tất cả các phần tử đều $< X$, trả về vị trí sau phần tử cuối cùng ($N$).
2. upper_bound (Tìm phần tử nhỏ nhất $> X$):

• Tìm vị trí đầu tiên mà giá trị tại đó $> X$.

• Vị trí phần tử lớn nhất $\le X$ chính là upper_bound - 1.

Ví dụ minh họa 2: Mảng có phần tử lặp lại

Cho mảng: $A = [1, 3, 5, 5, 5, 8, 12]$, tìm các mốc biên với $X = 5$:

• lower_bound(A.begin(), A.end(), 5) - A.begin() $\implies$ Trả về chỉ số 2 (số 5 đầu tiên).

• upper_bound(A.begin(), A.end(), 5) - A.begin() $\implies$ Trả về chỉ số 5 (phần tử đầu tiên $> 5$).

• Số lần xuất hiện của số 5: $\text{Count}(5) = \text{upper} - \text{lower} = 5 - 2 = \mathbf{3}$ phần tử.

• Vị trí xuất hiện cuối cùng của số 5: $\text{upper} - 1 = 5 - 1 = \mathbf{4}$.

3. Kỹ thuật chặt nhị phân trên tập kết quả (Binary Search on answer)

Đây là kỹ thuật cốt lõi trong các kỳ thi học sinh giỏi và Olympic tin học.

3.1. Nhận diện tính chất đơn điệu & phân loại 2 hướng

Trước khi cài đặt, bắt buộc phải xác định hướng biến thiên đơn điệu của hàm kiểm tra check(x):

• Hướng 1: Dạng True → False (Tìm giá trị $X$ LỚN NHẤT thỏa mãn):
• Đồ thị nghiệm: $[\text{True}, \text{True}, \dots, \text{True}, \mathbf{True_{\text{max}}}, \text{False}, \dots, \text{False}]$.
• Nếu check(mid) == true $\implies$ $mid$ thỏa mãn, ghi nhận ans = mid và tìm nghiệm lớn hơn ở bên phải: low = mid + 1.
• Nếu check(mid) == false $\implies$ $mid$ quá lớn, thu hẹp về bên trái: high = mid - 1.

• Ví dụ điển hình: Cắt gỗ lấy tối thiểu $M$ mét (độ cao cưa càng thấp càng nhiều gỗ $\implies$ tìm độ cao Max).

• Hướng 2: Dạng False → True (Tìm giá trị $X$ NHỎ NHẤT thỏa mãn):

• Đồ thị nghiệm: $[\text{False}, \text{False}, \dots, \text{False}, \mathbf{True_{\text{min}}}, \text{True}, \dots, \text{True}]$.
• Nếu check(mid) == true $\implies$ $mid$ thỏa mãn, ghi nhận ans = mid và tìm nghiệm nhỏ hơn ở bên trái: high = mid - 1.
• Nếu check(mid) == false $\implies$ $mid$ chưa đủ lớn, tăng giá trị lên: low = mid + 1.
• Ví dụ điển hình: Vận chuyển hàng trong $D$ ngày (tải trọng thuyền càng lớn càng dễ chở $\implies$ tìm tải trọng Min).

Ví dụ minh họa 3: Bài toán cắt gỗ lấy tối thiểu $M = 7$ mét gỗ

Cho $N = 4$ cây có chiều cao: $A = [20, 15, 10, 17]$. Cần tìm độ cao máy cưa $H$ lớn nhất sao cho tổng lượng gỗ thu được $\ge 7$.

• Không gian tìm kiếm: $low = 0, high = \max(A) = 20$.
• Hàm check(H): Tính tổng $\sum \max(0, A_i - H)$. Nếu $\ge 7 \implies$ True, ngược lại False.

Bảng mô phỏng từng bước chặt nhị phân:

4. Chặt nhị phân trên tập số thực (real-number Binary Search)

Khi đề bài yêu cầu tìm nghiệm thực với độ chính xác sai số tuyệt đối $\le 10^{-6}$:

• Vấn đề của điều kiện while (high - low > 1e-7): Khi khoảng cách giữa $low$ và $high$ đạt tới giới hạn độ phân giải của kiểu double (bit mantissa), phép tính trung điểm mid = (low + high) / 2.0 có thể bị làm tròn thành đúng $low$ hoặc $high$, khiến hiệu số $high - low$ không thể thu hẹp thêm, dẫn đến nguy cơ vòng lặp không tiến triển hoặc chạy vô hạn.

• Giải pháp chuẩn thi đấu: Sử dụng vòng lặp với số lần lặp cố định ($60 \dots 100$ lần): $$\text{Độ thu hẹp} = \frac{\text{high} - \text{low}}{2^{100}} \approx \frac{10^9}{1.26 \times 10^{30}} \approx 10^{-21} \ll 10^{-6}$$ Đảm bảo thuật toán luôn dừng đúng số bước, an toàn tuyệt đối và đạt độ chính xác tối đa của phần cứng.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1a: Tìm giá trị lớn nhất thỏa mãn (dạng True -> False)

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

// Hàm kiểm tra: Lượng gỗ thu được khi cưa ở độ cao mid có >= M hay không?
bool check(long long mid, const vector<long long>& a, long long m) {
    long long wood = 0;
    for (long long x : a) {
        if (x > mid) wood += (x - mid);

    }
    return wood >= m;
}

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

    int n;
    long long m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> a(n);

    long long max_val = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];

        max_val = max(max_val, a[i]);
    }

    long long low = 0, high = max_val;
    long long ans = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, a, m)) {
            ans = mid;        // Ghi nhận nghiệm hợp lệ
            low = mid + 1;    // Tìm giá trị lớn hơn ở bên phải
        } else {
            high = mid - 1;   // Không thỏa mãn, thu hẹp về bên trái
        }
    }

    cout << ans << "\n";
    return 0;
}

Mẫu 1b: Tìm giá trị nhỏ nhất thỏa mãn (dạng False -> True)

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

// Hàm kiểm tra: Với tải trọng phà là mid, có chở hết hàng trong <= D ngày hay không?
bool check(long long mid, const vector<long long>& w, int d) {
    int days = 1;
    long long current_load = 0;
    for (long long x : w) {
        if (current_load + x > mid) {

            days++;
            current_load = x;
        } else {
            current_load += x;
        }
    }
    return days <= d;
}

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

    int n, d;
    if (!(cin >> n >> d)) return 0;

    vector<long long> w(n);

    long long max_w = 0, sum_w = 0;
    for (int i = 0; i < n; ++i) {
        cin >> w[i];

        max_w = max(max_w, w[i]);
        sum_w += w[i];
    }

    // Không gian tìm kiếm: Tải trọng tối thiểu phải chở được kiện nặng nhất
    long long low = max_w, high = sum_w;
    long long ans = sum_w;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, w, d)) {
            ans = mid;        // Ghi nhận nghiệm hợp lệ
            high = mid - 1;   // Tìm giá trị nhỏ hơn ở bên trái
        } else {
            low = mid + 1;    // Tải trọng chưa đủ, phải tăng lên
        }
    }

    cout << ans << "\n";
    return 0;
}

Mẫu 2: Binary Search số thực (100 vòng lặp robust)

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

bool check_real(double mid) {
    return (mid * mid * mid + 2.0 * mid * mid + 10.0 * mid >= 100.0);
}

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

    double low = 0.0, high = 1e9;

    // Lặp cố định 100 lần để đạt sai số < 10^-15
    for (int iter = 0; iter < 100; ++iter) {
        double mid = low + (high - low) / 2.0;
        if (check_real(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }

    cout << fixed << setprecision(7) << low << "\n";
    return 0;
}

6. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy tràn số khi tính mid: Biểu thức $mid = (low + high)/2$ sẽ bị tràn số kiểu int 32-bit nếu $low + high \ge 2 \cdot 10^9$. Quy tắc bắt buộc: Luôn viết $mid = low + (high - low)/2$.
2. Bẫy vòng lặp vô tận (Infinite Loop): Khi không gian tìm kiếm chỉ còn 2 phần tử ($low = high - 1$), nếu cập nhật low = mid trong khi mid bị làm tròn xuống sẽ khiến $low$ không bao giờ tăng, gây TLE. Cần cập nhật low = mid + 1 hoặc high = mid - 1.
3. Bẫy biên không gian tìm kiếm $[low, high]$: Đặt $high$ quá nhỏ dẫn đến bỏ sót nghiệm đúng, hoặc đặt $low = 0$ dẫn đến lỗi chia cho 0 (mid = 0) trong hàm check.
4. Bẫy phần tử trùng lặp trong mảng xoay vòng: Nếu mảng xoay vòng có các phần tử trùng lặp thỏa mãn $A[low] == A[mid] == A[high]$, ta không thể xác định nửa nào được sắp xếp đơn điệu $\implies$ Trường hợp xấu nhất phải co cả hai đầu low++ và high--, làm độ phức tạp suy biến về $\mathcal{O}(N)$.

7. Ranh giới áp dụng: Khi nào nên & không nên dùng?

• KHI NÀO ÁP DỤNG:
• Không gian tìm kiếm có tính chất đơn điệu (Monotonic): Đồ thị hàm kiểm tra có dạng dải phân cách rõ ràng: $[\text{True}, \dots, \text{True}, \text{False}, \dots, \text{False}]$.
• Cần tối ưu nghiệm trên miền cực lớn ($1 \dots 10^{18}$) mà không thể duyệt tuần tự.
• KHI NÀO THẤT BẠI:
• Không gian tìm kiếm không đơn điệu (hàm dao động, có nhiều cực trị cục bộ). Lúc này chặt nhị phân sẽ bỏ sót nghiệm tối ưu toàn cục. Bắt buộc phải dùng Ternary Search (Tìm kiếm Tam phân) nếu hàm lồi/lõm, hoặc Quy hoạch động / Duyệt đồ thị.