Tìm hiểu Thuật Toán Tìm Kiếm Nhị Phân (Binary Search) trong C++

Thuật toán tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm hiệu quả và quan trọng trong lập trình. Bài viết này sẽ giải đáp các thắc mắc thường gặp về thuật toán tìm kiếm nhị phân, giúp bạn nắm vững kiến thức này.

Tìm Kiếm Nhị Phân là gì?

Tìm kiếm nhị phân (Binary Search) được áp 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. Điểm khác biệt so với tìm kiếm tuyến tính là tìm kiếm nhị phân yêu cầu dãy số phải được sắp xếp trước.

Ví dụ, nếu bạn muố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. Ban đầu, đoạn tìm kiếm là toàn bộ mảng, với chỉ số đầu tiên là 0 và chỉ số cuối cùng là N-1.

Ý tưởng cốt lõi của thuật toán là mỗi lần tìm kiếm trên đoạn [L, R], ta xác định phần tử ở giữa mảng và so sánh với X. Do mảng đã được sắp xếp, việc so sánh này cho phép ta loại bỏ một nửa khoảng tìm kiếm. Quá trình này lặp lại, khiến đoạn tìm kiếm giảm đi một nửa sau mỗi lần.

Ví dụ: với mảng 1 tỷ phần tử, bạn chỉ cần tối đa khoảng 31 lần tìm kiếm. Chỉ số giữa mảng được tính bằng (L + R) / 2 hoặc L + (R – L) / 2. Độ phức tạp của thuật toán là O(logN).

Mô tả thuật toán tìm kiếm nhị phân

Các bước thực hiện Tìm Kiếm Nhị Phân

1. Chia đôi: Chia đoạn tìm kiếm thành hai nửa bằng cách tìm chỉ số giữa M = (L + R) / 2.
2. So sánh: So sánh A[M] với X. Có ba trường hợp:
   • Trường hợp 1: A[M] == X => Tìm thấy X.
   • Trường hợp 2: A[M] < X => Loại bỏ nửa bên trái, cập nhật L = M + 1.
   • Trường hợp 3: A[M] > X => Loại bỏ nửa bên phải, cập nhật R = M – 1.
3. Lặp lại: Lặp lại bước 1 và 2 cho đến khi tìm thấy X hoặc không còn khoảng tìm kiếm (L > R).

Minh họa Tìm Kiếm Nhị Phân

Trường hợp 1: Tìm thấy phần tử ở giữa.

binary search 1

Trường hợp 2: Phần tử cần tìm nằm bên phải.

binary search 2

Trường hợp 3: Phần tử cần tìm nằm bên trái.

binary search 3

Ví dụ về Tìm Kiếm Nhị Phân

Ví dụ 1: Tìm X = 3 trong mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}.

1. L = 0, R = 9, M = 4, A[M] = 5 > X => R = 3
2. L = 0, R = 3, M = 1, A[M] = 1 < X => L = 2
3. L = 2, R = 3, M = 2, A[M] = 3 == X => Tìm thấy X.

Ví dụ 2: Tìm X = 2 trong mảng A[] = {1, 1, 3, 4, 5, 8, 9, 12, 21, 32}.

1. L = 0, R = 9, M = 4, A[M] = 5 > X => R = 3
2. L = 0, R = 3, M = 1, A[M] = 1 < X => L = 2
3. L = 2, R = 3, M = 2, A[M] = 3 > X => R = 1
4. L = 2, R = 1, L > R => Không tìm thấy X.

Các biến thể của Tìm Kiếm Nhị Phân

Tìm vị trí đầu tiên của X: Khi tìm thấy X, lưu kết quả và tiếp tục tìm kiếm bên trái.

Tìm vị trí cuối cùng của X: Khi tìm thấy X, lưu kết quả và tiếp tục tìm kiếm bên phải.

Tìm vị trí đầu tiên lớn hơn hoặc bằng X: Khi tìm thấy phần tử lớn hơn hoặc bằng X, lưu kết quả và tiếp tục tìm kiếm bên trái.

Mã nguồn C++ cho Tìm Kiếm Nhị Phân cơ bản

#include "iostream"
using namespace std;

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;
}

int main() {
    int n = 12, x = 24, y = 6;
    int a[12] = {1, 2, 3, 4, 5, 5, 7, 9, 13, 24, 27, 28};
    if (binary_search(a, n, x)) {
        cout << "FOUNDn";
    } else cout << "NOT FOUNDn";
    if (binary_search(a, n, y)) {
        cout << "FOUNDn";
    } else cout << "NOT FOUNDn";
    return 0;
}

Kết luận

Bài viết đã trình bày chi tiết về thuật toán tìm kiếm nhị phân, từ khái niệm, cách thức hoạt động, ví dụ minh họa đến mã nguồn C++. Hy vọng bài viết này hữu ích cho bạn trong việc học tập và áp dụng thuật toán tìm kiếm nhị phân.