Giải thích Binary Search (Tìm kiếm nhị phân) trong Python

Binary search (tìm kiếm nhị phân) là thuật toán tìm kiếm dùng để tìm một phần tử từ mảng đã sắp xếp. Không thể dùng để tìm từ mảng chưa sắp xếp. Binary search là thuật toán hiệu quả và tốt hơn linear search về độ phức tạp thời gian.

Độ phức tạp thời gian của linear search là O(n). Còn binary search là O(log n). Do đó, binary search hiệu quả và nhanh hơn nhưng chỉ dùng cho mảng đã sắp xếp.

Binary Search hoạt động như thế nào?

Ý tưởng cơ bản: thay vì so sánh phần tử cần tìm với tất cả phần tử của mảng, ta so sánh với phần tử giữa của mảng. Nếu trùng khớp, tìm kiếm thành công. Nếu phần tử cần tìm nhỏ hơn phần tử giữa, chắc chắn nó nằm ở nửa đầu (bên trái) của mảng vì mảng đã sắp xếp. Tương tự, nếu phần tử giữa, nó nằm ở nửa sau (bên phải).

Như vậy, Binary search liên tục giảm mảng xuống một nửa. Quá trình trên được áp dụng đệ quy trên nửa mảng được chọn cho đến khi tìm thấy phần tử cần tìm.

Bắt đầu với chỉ số trái l = 0 và chỉ số phải r = len(arr) - 1. Chỉ số giữa mid = (l + r) // 2. Nếu phần tử cần tìm nhỏ hơn phần tử giữa, đổi r = mid - 1 (chỉ xem nửa đầu). Ngược lại, nếu lớn hơn, đổi l = mid + 1 (chỉ xem nửa sau). Lặp lại cho nửa mảng được chọn.

Làm sao biết phần tử không có trong mảng?

Cần điều kiện dừng để chỉ ra phần tử không có. Ta lặp tìm kiếm miễn là l <= r. Khi điều kiện này sai mà chưa tìm thấy, nghĩa là phần tử không có trong mảng.

Ví dụ minh họa

Cho mảng đã sắp xếp sau, tìm phần tử 6.

L=0 H=8 Mid=4 → phần tử giữa là 10. 6 < 10 → lấy nửa đầu. H = Mid-1 = 3.

L=0 H=3 Mid=1 → phần tử giữa là 5. 6 > 5 → lấy nửa sau. L = Mid+1 = 2.

L=2 H=3 Mid=2 → phần tử giữa là 6. 6 == 6 → tìm thấy.

Phần tử 6 tìm thấy tại chỉ số 2.

Triển khai

Từ mảng đã sắp xếp cho trước, tìm phần tử cần tìm và in chỉ số nếu có. Nếu không có, in -1.

Ví dụ

def binary_search(arr, x):
    l = 0
    r = len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == x:
            return mid
        elif x < arr[mid]:
            r = mid - 1
        elif x > arr[mid]:
            l = mid + 1
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a = 7
print(binary_search(array, a))
b = 15
print(binary_search(array, b))

Kết quả

6
-1

Phần tử 7 có tại chỉ số 6.

Phần tử 15 không có trong mảng, in -1.