Tìm kiếm nhị phân (Binary Search) là thuật toán được sử dụng trên dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

Khác với tìm kiếm tuyến tính (Linear Search) không yêu cầu điều kiện về thứ tự, tìm kiếm nhị phân bắt buộc dãy phải có thứ tự. Nếu dãy chưa được sắp xếp, ta cần sắp xếp trước khi áp dụng thuật toán.

Mô tả bài toán

Giả sử cần tìm phần tử x trong mảng A gồm n phần tử đã được sắp xếp tăng dần.

• Chỉ số trái ban đầu: l = 0
• Chỉ số phải ban đầu: r = n − 1

Ở mỗi bước, xét đoạn tìm kiếm [l, r], ta chọn phần tử ở giữa để so sánh với x. Nhờ tính chất đã sắp xếp, sau mỗi lần so sánh ta có thể loại bỏ một nửa không gian tìm kiếm.

Ví dụ: Với mảng có 1 tỷ phần tử, thuật toán chỉ cần tối đa ~\log_2(10^9) ≈ 30~ lần so sánh.

Chỉ số giữa

Chỉ số giữa m được tính bằng một trong hai cách:

• ~m = (l + r) / 2~
• ~m = l + (r - l) / 2~ (an toàn hơn với số lớn)

Độ phức tạp

• Thời gian: ~O(\log n)~
• Bộ nhớ: ~O(1)~

Thuật toán

1. Khởi tạo l = 0, r = n − 1

2. Trong khi l ≤ r:

   • Tính m là chỉ số giữa
   • So sánh A[m] với x

3. Có 3 trường hợp:

   • Nếu A[m] = x → tìm thấy
   • Nếu A[m] < x → tìm nửa phải, cập nhật l = m + 1
   • Nếu A[m] > x → tìm nửa trái, cập nhật r = m − 1
4. Nếu l > r → không tìm thấy

Mã nguồn

bool binary_search(int a[], int n, int x){
    int l = 0, r = n - 1;
    while(l <= r){
        int m = (l + r) / 2;
        if(a[m] == x){
            return true;
        }
        else if(a[m] < x){
            l = m + 1;
        }
        else{
            r = m - 1;
        }
    }
    return false;
}

Ví dụ minh họa

Ví dụ 1: Tìm x = 3

Mảng: {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}

• Bước 1: l = 0, r = 9 → m = 4 → A[m] = 5 > 3 → r = 3
• Bước 2: l = 0, r = 3 → m = 1 → A[m] = 1 < 3 → l = 2
• Bước 3: l = 2, r = 3 → m = 2 → A[m] = 3 → tìm thấy

Ví dụ 2: Tìm x = 2

• Bước 1: l = 0, r = 9 → m = 4 → A[m] > x → r = 3
• Bước 2: l = 0, r = 3 → m = 1 → A[m] < x → l = 2
• Bước 3: l = 2, r = 3 → m = 2 → A[m] > x → r = 1
• l > r → không tìm thấy

2. Tìm kiếm nhị phân biến đổi

Bài toán 1: Tìm vị trí đầu tiên của x

Khi tìm thấy x, không dừng lại ngay mà tiếp tục tìm về bên trái để tìm vị trí xuất hiện đầu tiên.

int firstPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1;
    while(l <= r){
        int m = (l + r) / 2;
        if(a[m] == x){
            pos = m;
            r = m - 1;
        }
        else if(a[m] < x){
            l = m + 1;
        }
        else{
            r = m - 1;
        }
    }
    return pos;
}

Bài toán 2: Tìm vị trí cuối cùng của x

Khi tìm thấy x, tiếp tục tìm về bên phải.

int lastPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1;
    while(l <= r){
        int m = (l + r) / 2;
        if(a[m] == x){
            pos = m;
            l = m + 1;
        }
        else if(a[m] < x){
            l = m + 1;
        }
        else{
            r = m - 1;
        }
    }
    return pos;
}

Bài toán 3: Tìm vị trí đầu tiên có giá trị ≥ x

Khi A[m] ≥ x, lưu kết quả và tiếp tục tìm về bên trái.

int firstPos(int a[], int n, int x){
    int l = 0, r = n - 1;
    int pos = -1;
    while(l <= r){
        int m = (l + r) / 2;
        if(a[m] >= x){
            pos = m;
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
    return pos;
}