Tìm kiếm nhị phân (Binary Search) trong C++

Tìm kiếm nhị phân (binary search) là thuật toán tìm vị trí giá trị mục tiêu trong mảng đã sắp xếp. So sánh giá trị mục tiêu với phần tử giữa mảng. Nếu không bằng, loại bỏ nửa mảng không chứa mục tiêu và tiếp tục trên nửa còn lại. Lặp lại cho đến khi tìm thấy hoặc mảng rỗng.

Độ phức tạp: O(log n). Yêu cầu mảng phải được sắp xếp trước.

Ví dụ minh họa

int binarySearch(int low, int high, int key) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] < key)
            low = mid + 1;
        else if (a[mid] > key)
            high = mid - 1;
        else
            return mid;
    }
    return -1; // khong tim thay
}

Lưu ý: Mảng a[] phải được khai báo toàn cục hoặc truyền vào hàm. Tránh tràn số khi tính mid bằng low + (high - low) / 2.