Thuật toán tìm kiếm nhị phân: cách hoạt động, mã và độ phức tạp

Tìm kiếm nhị phân giải quyết vấn đề gì

Tìm kiếm tuyến tính kiểm tra từng phần tử và cần tới n phép so sánh. Nếu dữ liệu đã sắp xếp, bạn làm tốt hơn nhiều: so sánh mục tiêu với phần tử giữa là biết ngay nên giữ nửa nào. Đây cũng là cách bạn tra một từ trong từ điển giấy.

Tìm kiếm nhị phân còn dùng được cho mọi thứ có tính đơn điệu, không chỉ mảng. Nếu một điều kiện đúng/sai là sai với mọi giá trị nhỏ và đúng với mọi giá trị lớn, tìm kiếm nhị phân sẽ tìm ra ranh giới. Kỹ thuật này gọi là tìm kiếm nhị phân trên đáp án.

Ví dụ minh họa từng bước

Tìm 23 trong danh sách đã sắp xếp [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (chỉ số từ 0 đến 9). Giữ hai chỉ số lo và hi giới hạn phạm vi còn phải kiểm tra.

Ba phép so sánh thay vì sáu của duyệt tuyến tính. Với danh sách một triệu phần tử, tìm kiếm nhị phân cần tối đa 20 phép.

Cài đặt bằng Python

Phiên bản lặp dưới đây dùng đoạn đóng [lo, hi]: cả hai đầu vẫn là ứng viên. Vòng lặp chạy khi đoạn chưa rỗng.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

Trong mã Python thực tế, hãy dùng module thư viện chuẩn bisect. bisect_left trả về vị trí ngoài cùng bên trái nơi có thể chèn mục tiêu mà vẫn giữ list đã sắp xếp, qua đó cũng cho biết mục tiêu có tồn tại hay không.

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

Độ phức tạp thời gian và không gian

Các biến thể: đầu tiên, cuối cùng và tìm kiếm nhị phân trên đáp án

Nhiều bài không hỏi giá trị có tồn tại không mà hỏi ranh giới ở đâu: chỉ số đầu tiên có giá trị không nhỏ hơn x, lần xuất hiện cuối cùng của x, hoặc số nhỏ nhất thỏa một điều kiện. Hãy dùng đoạn nửa mở [lo, hi) và đừng bao giờ dừng sớm.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• Cận dưới (chỉ số đầu tiên có giá trị ≥ x): bisect_left.
• Cận trên (chỉ số đầu tiên có giá trị > x): bisect_right.
• Số lần x xuất hiện trong list đã sắp xếp: bisect_right(a, x) - bisect_left(a, x).
• Tìm trong mảng đã sắp xếp bị xoay, tìm đỉnh và cực tiểu hóa giá trị lớn nhất (ví dụ sức chứa nhỏ nhất để chở hết hàng trong D ngày) là các biến thể phỏng vấn kinh điển.

Lỗi thường gặp

• Trộn lẫn quy ước phạm vi. Với đoạn đóng dùng lo <= hi và hi = mid - 1; với đoạn nửa mở dùng lo < hi và hi = mid. Trộn lẫn gây vòng lặp vô hạn hoặc bỏ sót phần tử.
• Viết lo = mid thay vì lo = mid + 1. Khi hi = lo + 1, mid bằng lo và vòng lặp không bao giờ kết thúc.
• Chạy tìm kiếm nhị phân trên dữ liệu chưa sắp xếp. Nó trả về đáp án sai mà không báo lỗi.
• Tràn số nguyên trong (lo + hi) / 2 ở các ngôn ngữ có số nguyên kích thước cố định như Java, C và C++. Hãy dùng lo + (hi - lo) / 2. Số nguyên của Python không tràn, nên (lo + hi) // 2 an toàn.
• Trả về kết quả khớp đầu tiên tìm thấy khi đề yêu cầu lần xuất hiện đầu tiên trong các giá trị trùng.

Khi nào nên dùng tìm kiếm nhị phân

Ứng dụng thực tế gồm chỉ mục của cơ sở dữ liệu và hệ thống tệp (B-tree tổng quát hóa ý tưởng này), git bisect để tìm commit gây ra lỗi, tra giá trị trong bảng khoảng đã sắp xếp như các dải IP, và nhiều bài toán số học cần tìm một ngưỡng.