Trong các bài toán lập trình, thao tác tìm kiếm xuất hiện thường xuyên. Nếu sử dụng phương pháp tìm kiếm lực lượng (brute-force) với lượng dữ liệu lớn, chương trình sẽ gặp vấn đề về thời gian thực thi (ví dụ: với quy mô (10^5) thì độ phức tạp (O(n^2)) thường vượt quá thời gian cho phép, trong khi (O(nlogn)) thường chấp nhận được). Vì vậy, tìm kiếm nhị phân là một kỹ thuật tối ưu được sử dụng rộng rãi.

Mặc dù các hàm tìm kiếm nhị phân trong thư viện STL rất tiện dụng và phù hợp với các bài toán tìm kiếm trên khoảng, chúng ta vẫn cần nắm vững cách triển khai tìm kiếm nhị phân bằng C++. Như câu nói nổi tiếng: "Đây là một thuật toán đơn giản, nhưng những chi tiết của nó lại đáng ngạc nhiên phức tạp."

1. Triển khai Tìm kiếm Nhị phân bằng C++ =====================================

Ví dụ minh họa: Bài toán Tìm phạm vi của số Mô tả bài toán: Cho một mảng số nguyên đã được sắp xếp tăng dần có độ dài n, cùng với q truy vấn. Với mỗi truy vấn, trả về vị trí bắt đầu và kết thúc của phần tử k (vị trí được đánh số từ 0). Nếu phần tử này không tồn tại trong mảng, trả về -1 -1. (Phạm vi dữ liệu (10^5))

#include <iostream>
using namespace std;
const int MAX_SIZE = 100005;
int n, m, arr[MAX_SIZE];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    while (m--)
    {
        int target;
        scanf("%d", &target);
        int left = -1, right = n;
        while (left + 1 != right)
        {
            int mid = left + right >> 1;
            if (arr[mid] >= target) right = mid;
            else left = mid;
        }
        if (arr[right] != target) printf("-1 -1\n");
        else
        {
            printf("%d ", right);
            int left_bound = -1, right_bound = n;
            while (left_bound + 1 != right_bound)
            {
                int mid = left_bound + right_bound >> 1;
                if (arr[mid] <= target) left_bound = mid;
                else right_bound = mid;
            }
            if (arr[left_bound] != target) printf("%d\n", right);
            else printf("%d\n", left_bound);
        }
    }
    return 0;
}

Biến right và left_bound lần lượt tiến gần đến vị trí đầu tiên và cuối cùng của giá trị target. Nếu right không tồn tại, nghĩa là target không có trong mảng.

Phiên bản sử dụng STL thường chậm hơn phiên bản C++ thuần khoảng 5ms, sự khác biệt không đáng kể.

2. Sử dụng hàm STL để thực hiện Tìm kiếm Nhị phân ==============================================

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int data[5] = {8, 3, 6, 9, 2};
    int value = 6;
    // Mảng cần được sắp xếp trước khi tìm kiếm nhị phân
    sort(data, data + 5);
    // Vị trí của phần tử đầu tiên nhỏ hơn value
    int first_less = lower_bound(data, data + 5, value) - data - 1;
    // Vị trí của phần tử đầu tiên lớn hơn value
    int first_greater = upper_bound(data, data + 5, value) - data;
    cout << first_less << ' ' << first_greater << endl;
    // Kiểm tra sự tồn tại của một giá trị
    cout << binary_search(data, data + 5, 7);
    return 0;
}
Kết quả:
1 3
0

Lưu ý quan trọng:

1. lower_bound và upper_bound trả về lặp tử (iterator)
2. lower_bound và upper_bound mặc định yêu cầu mảng được sắp xếp tăng dần, nếu mảng giảm dần phải sử dụng:

    lower_bound(data, data + 5, value, greater<int>());

3. Nếu giá trị tìm kiếm không tồn tại, lower_bound và upper_bound trả về vị trí chèn giá trị mà không làm thay đổi thứ tự của mảng hiện tại
4. Trước khi gọi hàm, mảng phải được sắp xếp. Nếu thứ tự mảng không khớp với yêu cầu của hàm hoặc mảng chưa được sắp xếp, kết quả trả về sẽ không chính xác (giá trị -1 hoặc n)

Kiến thức liên quan

Sắp xếp giảm dần sử dụng std::sort Cách 1: Hàm so sánh tùy chỉnh cmp()

bool cmp(int x, int y)
{
    return x > y;
}

Cách 2:

sort(data, data + 5, greater<int>()); // Giảm dần
sort(data, data + 5, less<int>()); // Tăng dần