Tổng quan về thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân (Binary Search) là một kỹ thuật tối ưu dựa trên chiến lược chia để trị. Khác với lầm tưởng phổ biến rằng thuật toán này chỉ áp dụng được trên các dãy số có tính đơn điệu (tăng dần hoặc giảm dần), bản chất cốt lõi của tìm kiếm nhị phân nằm ở việc xác định điểm biên của một tính chất cụ thể trên một tập hợp dữ liệu.

Giả sử ta có một khoảng giá trị, trong đó một phần của khoảng thỏa mãn tính chất P và phần còn lại thì không. Mục tiêu của tìm kiếm nhị phân là thu hẹp phạm vi để tìm ra ranh giới giữa hai vùng này.

1. Tìm kiếm nhị phân trên số nguyên

Đối với số nguyên, thách thức lớn nhất thường nằm ở việc xử lý các giá trị biên để tránh vòng lặp vô tận do phép chia số nguyên trong C++ luôn làm tròn xuống.

Mô hình 1: Tìm điểm đầu tiên thỏa mãn tính chất bên phải

Giả sử chúng ta cần tìm vị trí nhỏ nhất i sao cho phần tử tại đó thỏa mãn một điều kiện nhất định (ví dụ: phần tử đầu tiên lớn hơn hoặc bằng X).

int search_lower_bound(int left, int right) {
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check_condition(mid)) {
            right = mid; // Kết quả nằm ở bên trái hoặc ngay tại mid
        } else {
            left = mid + 1; // Kết quả chắc chắn nằm ở bên phải mid
        }
    }
    return left;
}

Mô hình 2: Tìm điểm cuối cùng thỏa mãn tính chất bên trái

Khi cần tìm vị trí lớn nhất i thỏa mãn điều kiện (ví dụ: phần tử cuối cùng nhỏ hơn hoặc bằng X), ta cần điều chỉnh cách tính mid để tránh lỗi logic.

int search_upper_bound(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) >> 1; // Cộng 1 để làm tròn lên
        if (check_condition(mid)) {
            left = mid; // Kết quả nằm ở bên phải hoặc ngay tại mid
        } else {
            right = mid - 1; // Kết quả chắc chắn nằm ở bên trái mid
        }
    }
    return left;
}

Lưu ý quan trọng: Tại sao cần + 1 khi tính mid? Trong C++, khi left = right - 1, nếu ta dùng mid = (left + right) / 2 thì mid sẽ bằng left. Nếu điều kiện check(mid) trả về true và ta gán left = mid, vòng lặp sẽ bị kẹt mãi mãi. Việc + 1 giúp mid tiến về phía right, giải quyết triệt để vấn đề này.

Bài toán thực tế: Xác định phạm vi của phần tử trong mảng

Cho một mảng số nguyên đã sắp xếp, hãy tìm chỉ số bắt đầu và kết thúc của một số target. Nếu không tìm thấy, trả về -1 -1.

#include <iostream>
#include <vector>

using namespace std;

void find_range(const vector<int>& arr, int target) {
    int n = arr.size();
    if (n == 0) {
        cout << "-1 -1" << endl;
        return;
    }

    // Tìm biên trái (vị trí đầu tiên >= target)
    int left = 0, right = n - 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }

    if (arr[left] != target) {
        cout << "-1 -1" << endl;
    } else {
        int start_idx = left;
        // Tìm biên phải (vị trí cuối cùng <= target)
        left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (arr[mid] <= target) left = mid;
            else right = mid - 1;
        }
        cout << start_idx << " " << left << endl;
    }
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> data(n);
    for (int i = 0; i < n; i++) scanf("%d", &data[i]);

    while (q--) {
        int val;
        scanf("%d", &val);
        find_range(data, val);
    }
    return 0;
}

2. Tìm kiếm nhị phân trên số thực

Tìm kiếm nhị phân trên tập số thực đơn giản hơn về mặt logic vì không gặp phải vấn đề làm tròn của số nguyên. Thay vì so sánh left < right, chúng ta lặp cho đến khi khoảng cách giữa left và right đủ nhỏ (đạt độ chính xác yêu cầu).

Ví dụ: Tính căn bậc hai của một số thực

#include <iostream>
#include <iomanip>

using namespace std;

double square_root(double n) {
    double left = 0, right = max(1.0, n);
    // Duy trì độ chính xác 10^-8
    for (int i = 0; i < 100; i++) { // Hoặc dùng while (right - left > 1e-8)
        double mid = (left + right) / 2.0;
        if (mid * mid >= n) right = mid;
        else left = mid;
    }
    return left;
}

int main() {
    double val;
    if (cin >> val) {
        cout << fixed << setprecision(6) << square_root(val) << endl;
    }
    return 0;
}

Đối với số thực, việc sử dụng một số vòng lặp cố định (khoảng 100 lần) thường an toàn hơn việc so sánh right - left > epsilon để tránh các vấn đề về độ chính xác của kiểu dữ liệu double.