Tìm kiếm nhị phân (Khoảng mở - mở)

Trước khi triển khai, hãy cùng tìm hiểu cách hoạt động của thuật toán tìm kiếm nhị phân. Chúng ta sẽ chia một mảng thành hai phần: màu đỏ và màu xanh. Màu xanh đại diện cho các phần tử thỏa mãn một điều kiện nhất định, trong khi màu đỏ đại diện cho các phần tử không thỏa mãn (tương tự như đèn giao thông, đèn đỏ thì dừng, đèn xanh thì đi).

Hàm kiểm tra màu xanh

Để xác định một phần tử là màu xanh hay màu đỏ, chúng ta có thể sử dụng một hàm riêng. Trong ví dụ này, một phần tử được coi là màu xanh (giá trị 1) nếu nó bằng với giá trị mục tiêu, ngược lại là màu đỏ (giá trị 0).

bool kiemTraXanh(int giaTri, int mucTieu) {
    return giaTri == mucTieu;
}

Mẫu tìm kiếm nhị phân (Khoảng mở - mở)

Mẫu này sử dụng hai con trỏ, một ở phía trái (màu đỏ) và một ở phía phải (màu xanh).

int timKiemNhiPhan(const vector<int>& mang, int mucTieu) {
    int trai = -1; // Con trỏ màu đỏ, chỉ vào phần tử cuối cùng của phần màu đỏ
    int phai = mang.size(); // Con trỏ màu xanh, chỉ vào phần tử đầu tiên của phần màu xanh

    // Tiếp tục thu hẹp khoảng cho đến khi khoảng chỉ còn hai phần tử
    while (trai + 1 < phai) {
        int giua = trai + (phai - trai) / 2; // Tính chỉ số trung bình của khoảng

        // Kiểm tra phần tử ở giữa là màu xanh hay màu đỏ
        if (kiemTraXanh(mang[giua], mucTieu)) {
            phai = giua; // Nếu màu xanh, di chuyển con trỏ màu xanh về phía trái
        } else {
            trai = giua; // Nếu màu đỏ, di chuyển con trỏ màu đỏ về phía phải
        }
    }
    // Trả về vị trí đầu tiên của phần màu xanh
    return phai;
}

Mẫu tìm kiếm nhị phân (Khoảng đóng - đóng)

Mẫu này sử dụng khoảng có cả hai đầu là đóng.

int timKiemDuoi(const vector<int>& mang, int mucTieu) {
    int trai = 0; // Khoảng bắt đầu từ [0, n-1]
    int phai = mang.size() - 1;

    while (trai <= phai) { // Vòng lặp chạy khi khoảng không rỗng
        int giua = trai + (phai - trai) / 2;

        if (mang[giua] < mucTieu) {
            trai = giua + 1; // Tìm trong nửa phải: [giua+1, phai]
        } else {
            phai = giua - 1; // Tìm trong nửa trái: [trai, giua-1]
        }
    }
    // Trả về vị trí đầu tiên của phần màu xanh (giá trị >= mục tiêu)
    return trai;
}

Mẫu tìm kiếm nhị phân (Khoảng đóng - mở)

Mẫu này sử dụng khoảng có đầu trái là đóng và đầu phải là mở.

int timKiemDuoi(const vector<int>& mang, int mucTieu) {
    int trai = 0; // Khoảng bắt đầu từ [0, n)
    int phai = mang.size();

    while (trai < phai) { // Vòng lặp chạy khi khoảng không rỗng
        int giua = trai + (phai - trai) / 2;

        if (mang[giua] < mucTieu) {
            trai = giua + 1; // Tìm trong nửa phải: [giua+1, phai)
        } else {
            phai = giua; // Tìm trong nửa trái: [trai, giua)
        }
    }
    // Cả trai và phai đều chỉ vào vị trí đầu tiên của phần màu xanh
    return trai;
}

Mẫu tìm kiếm nhị phân (Khoảng mở - mở)

Mẫu này sử dụng khoảng có cả hai đầu là mở.

int timKiemDuoi(const vector<int>& mang, int mucTieu) {
    int trai = -1; // Khoảng bắt đầu từ (-1, n)
    int phai = mang.size();

    while (trai + 1 < phai) { // Vòng lặp chạy khi khoảng không rỗng
        int giua = trai + (phai - trai) / 2;

        if (mang[giua] < mucTieu) {
            trai = giua; // Tìm trong nửa phải: (giua, phai)
        } else {
            phai = giua; // Tìm trong nửa trái: (trai, giua)
        }
    }
    // Trả về vị trí đầu tiên của phần màu xanh
    return phai;
}