Các hàm Binary Search trong C++ STL

Tìm kiếm nhị phân yêu cầu dãy đã sắp xếp. C++ STL cung cấp các hàm trong <algorithm>:

• binary_search(first, last, val) – Trả về true nếu tìm thấy val, ngược lại false. Độ phức tạp O(log n).
• lower_bound(first, last, val) – Trả về iterator đến vị trí đầu tiên có giá trị không nhỏ hơn val (>= val).
• upper_bound(first, last, val) – Trả về iterator đến vị trí đầu tiên có giá trị lớn hơn val (> val).

Khoảng cách giữa upper_bound và lower_bound cho biết số lần xuất hiện của val.

Ví dụ mã

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

int main() {
    vector<int> a = {6, 7, 10, 14, 16, 20};

    if (binary_search(a.begin(), a.end(), 50))
        cout << "50 tồn tại\n";
    else
        cout << "50 không tồn tại\n";

    if (binary_search(a.begin(), a.end(), 7))
        cout << "7 tồn tại\n";
    else
        cout << "7 không tồn tại\n";

    cout << "Vị trí lower_bound(7): " << lower_bound(a.begin(), a.end(), 7) - a.begin() << endl;
    cout << "Vị trí upper_bound(7): " << upper_bound(a.begin(), a.end(), 7) - a.begin() << endl;

    return 0;
}

Kết quả

50 không tồn tại
7 tồn tại
Vị trí lower_bound(7): 1
Vị trí upper_bound(7): 2

Giải thích: Phần tử 7 ở chỉ số 1. lower_bound trỏ đến 7 (chỉ số 1), upper_bound trỏ đến 10 (chỉ số 2).