Tìm kiếm nhị phân

1. Khái niệm

• Tìm kiếm nhị phân (Binary Search) là kỹ thuật tìm kiếm phần tử trong mảng đã được sắp xếp bằng cách chia đôi dãy số nhiều lần.
• Ý tưởng:
  • So sánh phần tử cần tìm (x) với giá trị ở giữa (a[mid]).
  • Nếu (a[mid] == x) → tìm thấy.
  • Nếu (x < a[mid]) → tìm trong nửa bên trái.
  • Nếu (a[mid] < x) → tìm trong nửa bên phải.
• Độ phức tạp: O(log n).

2. Cài đặt cơ bản

// Hàm tìm kiếm nhị phân cơ bản
// Trả về chỉ số (index) của phần tử x trong mảng a[0..n-1]
// Nếu không tìm thấy thì trả về -1
int binarySearch(vector<int>& a, int n, int x) {
    int l = 0;         // biến l: biên trái của đoạn đang xét
    int r = n - 1;     // biến r: biên phải của đoạn đang xét

    // Khi l <= r, nghĩa là đoạn [l, r] vẫn còn phần tử để kiểm tra
    while (l <= r) {
        int mid = l + (r-l) / 2;  // chỉ số giữa đoạn [l, r]

        if (a[mid] == x) 
            return mid;   // tìm thấy x tại vị trí mid

        if (a[mid] < x)  
            // Nếu giá trị ở giữa nhỏ hơn x,
            // thì x (nếu có) phải nằm bên phải
            l = mid + 1;
        else             
            // Nếu giá trị ở giữa lớn hơn x,
            // thì x (nếu có) phải nằm bên trái
            r = mid - 1;
    }

    return -1;  // không tìm thấy x trong mảng
}

Lưu ý: Có một số tài liệu sử dụng công thức tính mid = (l+r) / 2.

3. Các biến thể thường dùng

(a) Tìm vị trí xuất hiện đầu tiên của x

int BSfirstPos(vector<int>& a, int n, int x) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r-l) / 2;
        if (a[mid] >= x) {
            if (a[mid] == x) ans = mid;
            r = mid - 1;  // ép tìm sang trái
        } else l = mid + 1;
    }
    return ans;
}

(b) Tìm vị trí xuất hiện cuối cùng của x

int BSlastPos(vector<int>& a, int n, int x) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r-l) / 2;
        if (a[mid] <= x) {
            if (a[mid] == x) ans = mid;
            l = mid + 1;  // ép tìm sang phải
        } else r = mid - 1;
    }
    return ans;
}

(c) Tìm vị trí của giá trị nhỏ nhất ≥ x

int BSlowerBound(vector<int>& a, int n, int x) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r-l) / 2;
        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;  // vẫn có thể còn nhỏ hơn bên trái
        } else l = mid + 1;
    }
    return ans;
}

(d) Tìm vị trí của giá trị lớn nhất ≤ x

int BSupperBound(vector<int>& a, int n, int x) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r-l) / 2;
        if (a[mid] <= x) {
            ans = mid;
            l = mid + 1;  // vẫn có thể còn lớn hơn bên phải
        } else r = mid - 1;
    }
    return ans;
}

4. Ứng dụng trong các bài toán

1. Đếm số lần xuất hiện của x trong mảng
   → dùng BSfirstPos và BSlastPos.
2. Tìm vị trí chèn hợp lý để giữ mảng tăng dần
   → dùng BSlowerBound.
3. Giải bài toán tham lam / tối ưu:
   • Chia kẹo, chia nhóm, tìm kích thước lớn nhất thỏa điều kiện.
   • Tìm số lượng vật phẩm tối đa có thể chọn dưới giới hạn chi phí.
   • Tìm nghiệm của phương trình (ví dụ: căn bậc hai gần đúng).

5. Ví dụ minh họa

Ví dụ 1: Đếm số lần xuất hiện

// Input: a = {1,2,2,2,3,4}, x = 2
// Output: 3
int BScntOccurrences(vector<int>& a, int n, int x) {
    int f = firstPos(a, n, x);
    int l = lastPos(a, n, x);
    if (f == -1) return 0;
    return l - f + 1;
}

Ví dụ 2: Tìm căn bậc hai (số nguyên lớn nhất ≤ sqrt(x))

int BSintSqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

👉 Tìm kiếm nhị phân không chỉ để tìm phần tử trong mảng mà còn để giải quyết nhiều bài toán tối ưu khác, bằng cách xây dựng hàm kiểm tra điều kiện và tìm nghiệm trong đoạn.

Sau khi đã hiểu rõ kỹ thuật tìm kiếm nhị phân thì bạn hoàn toàn có thể tự tin sử dụng các hàm có sẵn từ thư viện std như binarysearch , upper_bound, lower_bound để giúp việc xử lý các bài toán có liên quan được thuận tiện và nhanh chóng hơn.