0

Thuật toán & CTDL #06: Binary Search - tìm 1 phần tử trong 1 tỷ chỉ cần 30 bước

Tìm một người trong một tỷ người mà chỉ cần 30 câu hỏi? Nghe như ảo thuật, nhưng đó là tìm kiếm nhị phân (binary search). Ý tưởng thì ai cũng hiểu trong 10 giây, nhưng viết đúng thì lại là chuyện khác: có cả một nghiên cứu nổi tiếng cho thấy phần lớn lập trình viên chuyên nghiệp viết binary search bị lỗi ở lần đầu. Bài này đi qua ý tưởng, một ví dụ chạy tay, và các cái bẫy hay gặp.

Ý tưởng

Điều kiện duy nhất: mảng phải được sắp xếp.

Thay vì dò từng ô từ trái sang phải, ta nhìn ô chính giữa:

  • Bằng giá trị cần tìm: xong.
  • Nhỏ hơn: giá trị cần tìm (nếu có) chắc chắn nằm ở nửa phải. Vứt luôn cả nửa trái.
  • Lớn hơn: vứt cả nửa phải.

Lặp lại trên nửa còn lại. Mỗi bước, vùng tìm kiếm giảm còn một nửa.

Chạy tay một ví dụ

Mảng trong video, 12 phần tử đã sắp:

chỉ số: 0  1   2   3   4   5   6   7   8   9   10  11
giá trị: 3  8  14  21  27  35  42  56  63  71  84  95

Tìm 84.

Cách ngây thơ (tìm tuần tự): dò 3, 8, 14, ... đến 84 ở chỉ số 10. Mất 11 bước.

Binary search với lo, hi là hai đầu vùng tìm kiếm, mid = (lo + hi) // 2:

Bước lo hi mid a[mid] Kết luận
1 0 11 5 35 35 < 84, vứt nửa trái, lo = 6
2 6 11 8 63 63 < 84, vứt nửa trái, lo = 9
3 9 11 10 84 Tìm thấy

3 bước thay vì 11.

Code Python

def binary_search(a, target):
    lo, hi = 0, len(a) - 1           # vùng tìm kiếm đóng [lo, hi]
    while lo <= hi:                  # <= vì lo == hi vẫn còn 1 phần tử
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1             # +1: mid đã xét rồi
        else:
            hi = mid - 1
    return -1                        # không có

a = [3, 8, 14, 21, 27, 35, 42, 56, 63, 71, 84, 95]
print(binary_search(a, 84))  # 10
print(binary_search(a, 50))  # -1
print(binary_search([], 1))  # -1

Trong code thật, Python có sẵn module bisect:

from bisect import bisect_left

a = [3, 8, 14, 21, 27, 35, 42, 56, 63, 71, 84, 95]
i = bisect_left(a, 84)                  # vị trí đầu tiên có a[i] >= 84
print(i, i < len(a) and a[i] == 84)     # 10 True

Độ phức tạp

  • Thời gian: O(log n). Số bước tối đa là ⌊log₂ n⌋ + 1.
    • 12 phần tử: tối đa 4 bước.
    • 1 tỷ phần tử: 2³⁰ ≈ 1,07 tỷ, nên tối đa 30 bước.
    • 1 nghìn tỷ phần tử: khoảng 40 bước. Dữ liệu tăng 1.000 lần, số bước chỉ thêm 10.
  • Tốt nhất: O(1), khi phần tử cần tìm nằm ngay giữa.
  • Bộ nhớ: O(1) với bản vòng lặp. Bản đệ quy tốn O(log n) stack.

So với tìm tuần tự O(n): với 1 tỷ phần tử là 30 bước so với tới 1 tỷ bước.

Khi nào dùng, khi nào không

Dùng khi:

  • Dữ liệu đã sắp xếp và được tìm nhiều lần. Sắp một lần O(n log n), sau đó mỗi lần tìm chỉ O(log n).
  • Tìm biên: phần tử đầu tiên ≥ x, vị trí chèn để giữ thứ tự (bisect_left, bisect_right).
  • Binary search trên đáp án: bài toán có tính đơn điệu kiểu "nếu làm được với X thì làm được với mọi giá trị lớn hơn X". Ví dụ tìm sức chứa nhỏ nhất của xe tải để chở hết hàng trong D ngày.
  • Ngoài đời: git bisect tìm commit gây lỗi trong hàng nghìn commit chỉ với khoảng chục lần kiểm tra. Index B-tree trong database cũng dựa trên cùng ý tưởng thu hẹp vùng tìm kiếm theo thứ tự.

Không dùng khi:

  • Dữ liệu chưa sắp và chỉ tìm một lần: sắp xếp mất O(n log n), đắt hơn tìm tuần tự O(n).
  • Linked list: không truy cập ô giữa trong O(1) được, binary search mất ý nghĩa.
  • Chỉ cần kiểm tra "có hay không" và dữ liệu thay đổi liên tục: hash table (bài 15) cho O(1) trung bình.

Lỗi hay gặp

  1. Vòng lặp vô hạn: viết lo = mid thay vì lo = mid + 1. Khi lo và hi kề nhau, mid luôn bằng lo, vùng tìm kiếm không bao giờ thu hẹp.
  2. Lệch một (off-by-one): trộn hai quy ước. Nếu hi = len(a) - 1 (khoảng đóng) thì dùng while lo <= hi và hi = mid - 1. Nếu hi = len(a) (khoảng nửa mở) thì dùng while lo < hi và hi = mid. Chọn một kiểu và nhất quán.
  3. Tràn số khi tính mid: trong Java/C/C++, (lo + hi) / 2 có thể tràn int khi mảng rất lớn. Lỗi này từng nằm trong Arrays.binarySearch của Java gần 10 năm trước khi được phát hiện năm 2006. Cách an toàn: lo + (hi - lo) / 2. Python dùng số nguyên không giới hạn nên không bị.
  4. Quên điều kiện sắp xếp: chạy binary search trên mảng chưa sắp không báo lỗi, chỉ trả về kết quả sai.
  5. Phần tử trùng: bản cơ bản trả về một vị trí bất kỳ của giá trị đó, không nhất thiết là đầu tiên. Cần vị trí đầu/cuối thì dùng bisect_left/bisect_right.

Câu hỏi phỏng vấn hay gặp

  • 1 tỷ phần tử cần tối đa bao nhiêu bước? 30.
  • Tìm vị trí đầu tiên và cuối cùng của x trong mảng có phần tử trùng? Hai lần binary search tìm biên.
  • Tìm trong mảng đã sắp nhưng bị xoay (rotated sorted array)? Vẫn O(log n): mỗi bước, ít nhất một nửa là đã sắp, kiểm tra target có nằm trong nửa đó không.
  • Căn bậc hai nguyên của n? Binary search trên đáp án trong khoảng [0, n].

Lời kết

Binary search là ví dụ đẹp nhất về sức mạnh của log n, và cũng nhắc rằng một thuật toán "dễ" vẫn đáng được viết cẩn thận. Đây cũng là lý do lớn khiến sắp xếp ở các bài trước quan trọng: có thứ tự thì mới tìm nhanh được.

Đây là bài 06/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình so sánh dò từng ô với vứt một nửa mỗi bước nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252

Bạn đã từng viết binary search bị lặp vô hạn chưa? Hãy kể trong phần bình luận.

Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.

Bài tiếp theo: Two Pointers - từ hai vòng for O(n²) xuống O(n) với bài tìm cặp có tổng cho trước


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí