Các hàm tìm kiếm nhị phân trong C++ STL: binary_search, lower_bound, upper_bound

Tìm kiếm nhị phân là thuật toán so sánh phần tử với giá trị giữa và chia mảng dựa trên kết quả, lặp lại cho đến khi tìm thấy. Mảng phải được sắp xếp trước khi áp dụng. Độ phức tạp thời gian là O(log n), do đó các hàm tiện ích trong STL rất quan trọng để giảm thời gian lập trình.

1. lower_bound

Trả về vị trí (iterator) của phần tử không nhỏ hơn giá trị cho trước (phần tử đầu tiên >= value).

Cú pháp

lower_bound(start_pointer, end_pointer, element)

Tham số

• start_pointer: con trỏ đến đầu cấu trúc.
• end_pointer: con trỏ đến cuối cấu trúc.
• element: giá trị cần tìm.

Giá trị trả về

• Nếu phần tử xuất hiện một lần → trả về vị trí của nó.
• Nếu xuất hiện nhiều lần → trả về vị trí đầu tiên.
• Nếu không xuất hiện → trả về vị trí của phần tử lớn hơn nó ngay tiếp theo.

Chỉ số thực tế = iterator trả về - iterator bắt đầu.

Ví dụ

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

int main() {
    vector<int> a1 = {2, 5, 7, 8, 15, 20};
    vector<int> a2 = {2, 3, 4, 6, 9, 23};
    vector<int> a3 = {2, 5, 7, 7, 15, 20};

    cout << "Vi tri cua 7 bang lower_bound:\n";
    cout << "Truong hop 1 (xuat hien 1 lan): " << lower_bound(a1.begin(), a1.end(), 7) - a1.begin() << "\n";
    cout << "Truong hop 2 (xuat hien nhieu lan): " << lower_bound(a3.begin(), a3.end(), 7) - a3.begin() << "\n";
    cout << "Truong hop 3 (khong xuat hien): " << lower_bound(a2.begin(), a2.end(), 7) - a2.begin() << "\n";
    return 0;
}

Kết quả

Vi tri cua 7 bang lower_bound:
Truong hop 1 (xuat hien 1 lan): 2
Truong hop 2 (xuat hien nhieu lan): 2
Truong hop 3 (khong xuat hien): 4

2. upper_bound

Trả về vị trí của phần tử lớn hơn giá trị cho trước (phần tử đầu tiên > value).

Cú pháp

upper_bound(start_pointer, end_pointer, element)

Giá trị trả về

• Nếu phần tử xuất hiện một lần → trả về vị trí phần tử lớn hơn nó ngay tiếp theo.
• Nếu xuất hiện nhiều lần → trả về vị trí sau phần tử cuối cùng bằng giá trị đó.
• Nếu không xuất hiện → trả về vị trí phần tử lớn hơn nó ngay tiếp theo.

Ví dụ

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

int main() {
    vector<int> a1 = {2, 5, 7, 8, 15, 20};
    vector<int> a2 = {2, 3, 4, 6, 9, 23};
    vector<int> a3 = {2, 5, 7, 7, 15, 20};

    cout << "Vi tri cua 7 bang upper_bound:\n";
    cout << "Truong hop 1: " << upper_bound(a1.begin(), a1.end(), 7) - a1.begin() << "\n";
    cout << "Truong hop 2: " << upper_bound(a3.begin(), a3.end(), 7) - a3.begin() << "\n";
    cout << "Truong hop 3: " << upper_bound(a2.begin(), a2.end(), 7) - a2.begin() << "\n";
    return 0;
}

Kết quả

Vi tri cua 7 bang upper_bound:
Truong hop 1: 3
Truong hop 2: 4
Truong hop 3: 4

3. binary_search

Kiểm tra xem phần tử có tồn tại trong cấu trúc hay không.

Cú pháp

binary_search(start_pointer, end_pointer, element)

Giá trị trả về

Trả về true nếu tìm thấy, ngược lại false.

Ví dụ

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

int main() {
    vector<int> arr = {6, 15, 21, 27, 39, 42};
    cout << "Tim 21: ";
    if (binary_search(arr.begin(), arr.end(), 21)) cout << "Tim thay\n"; else cout << "Khong tim thay\n";
    cout << "Tim 5: ";
    if (binary_search(arr.begin(), arr.end(), 5)) cout << "Tim thay\n"; else cout << "Khong tim thay\n";
    return 0;
}

Kết quả

Tim 21: Tim thay
Tim 5: Khong tim thay