Điều kiện áp dụng tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân chỉ hoạt động hiệu quả trên các cấu trúc dữ liệu đã được sắp xếp sẵn. Điều kiện tiên quyết là mảng phải có tính chất đơn điệu, cụ thể là đơn điệu không giảm hoặc đơn điệu không tăng.

• Đơn điệu không giảm: Các phần tử tăng dần nhưng cho phép các phần tử liền kề bằng nhau
• Đơn điệu không tăng: Các phần tử giảm dần nhưng cho phép các phần tử liền kề bằng nhau

Ví dụ minh họa:

• [2, 6, 6, 12, 25] - thỏa mãn tính đơn điệu
• [3, 11, 11, 8, 19] - không thỏa mãn tính đơn điệu
• [14, 10, 10, 5, 5, 0] - thỏa mãn tính đơn điệu

Hàm binary_search trong thư viện chuẩn C++

Hàm binary_search là một thành phần của thư viện tiêu chuẩn STL, được sử dụng để kiểm tra xem một phần tử có tồn tại trong dãy đã được sắp xếp hay không. Thuật toán này hoạt động bằng cách chia đôi dãy liên tục để tìm kiếm, qua đó giảm độ phức tạp xuống mức logarithmic.

Hàm trả về giá trị boolean: true nếu tìm thấy phần tử, false trong trường hợp ngược lại. Để lấy được vị trí của phần tử, cần sử dụng kết hợp các hàm lower_bound hoặc upper_bound.

#include 
using namespace std;

int main() {
    
    vector<int> data = {4, 8, 12, 16, 20};
    int searchValue = 12;
    
    bool exists = binary_search(data.begin(), data.end(), searchValue);
    if(exists) {
        cout << "Gia tri " << searchValue << " ton tai trong mang." << endl;    
    } else {
        cout << "Gia tri " << searchValue << " khong ton tai trong mang." << endl;
    }
    
    return 0;
}

Hai hàm hỗ trợ tìm kiếm: lower_bound và upper_bound

Cả hai hàm lower_bound và upper_bound đều nằm trong thư viện <algorithm>, phục vụ cho việc tìm kiếm trong dãy đã được sắp xếp. Chúng thường được dùng để xác định vị trí chèn phần tử hoặc đếm số lượng phần tử trong một khoảng cho trước.

Yêu cầu: Mảng phải được sắp xếp theo thứ tự tăng dần (cho phép các phần tử trùng lặp). Trong trường hợp cần tìm kiếm trên dãy giảm dần, có thể tùy chỉnh hàm so sánh tương tự như khi sử dụng với hàm sort.

Cơ chế hoạt động:

• lower_bound(vitribatdau, vitriketthuc, giatri): Trả về iterator trỏ đến phần tử đầu tiên có giá trị lớn hơn hoặc bằng giá trị cần tìm
• upper_bound(vitribatdau, vitriketthuc, giatri): Trả về iterator trỏ đến phần tử đầu tiên có giá trị lớn hơn giá trị cần tìm
• Nếu không tìm thấy, hàm trả về vị trí sau phần tử cuối cùng (tương đương với end())

Để chuyển đổi iterator sang chỉ số mảng, ta lấy hiệu số giữa iterator trả về và iterator của phần tử đầu tiên.

#include 
using namespace std;

int main() {
    
    vector<int> arr = {6, 2, 9, 4, 15, 22, 11};
    
    sort(arr.begin(), arr.end());
    
    for(const auto& item : arr) {
        cout << item << " ";
    }
    cout << "\n";
    
    int searchKey = 10;
    int position = lower_bound(arr.begin(), arr.end(), searchKey) - arr.begin();
    
    cout << "Vi tri phan tu dau tien >= " << searchKey << ": " << position << endl;
    
    return 0;
}