Binary search hoạt động như thế nào, và nó yêu cầu những gì?

Question

Accepted Answer

**Binary search** tìm một giá trị mục tiêu trong một mảng **đã được sắp xếp** bằng cách liên tục chia đôi phạm vi tìm kiếm. Mỗi lần so sánh loại bỏ một nửa số phần tử còn lại, cho ra thời gian **O(log n)**. ## Ý tưởng Xét phần tử ở giữa. Nếu nó bằng giá trị mục tiêu, xong. Nếu mục tiêu nhỏ hơn, tìm ở nửa trái; nếu lớn hơn, tìm ở nửa phải. Lặp lại cho đến khi tìm thấy hoặc phạm vi rỗng. ## Ví dụ ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # chỉ số ở giữa if arr[mid] == target: return mid # tìm thấy elif arr[mid] < target: lo = mid + 1 # loại bỏ nửa trái else: hi = mid - 1 # loại bỏ nửa phải return -1 # không tồn tại binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Truy vết ```text Tìm 7 trong [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Độ phức tạp - **Thời gian:** O(log n). **Bộ nhớ:** O(1) khi cài đặt lặp. ## Những cạm bẫy **Đầu vào phải được sắp xếp** — nếu không kết quả sẽ vô nghĩa. Cẩn thận với lỗi sai-một-đơn-vị (off-by-one) ở `lo`/`hi` và tràn số nguyên trong một số ngôn ngữ (dùng `lo + (hi-lo)//2`). ## Tại sao điều này quan trọng Việc chia đôi không gian tìm kiếm biến một phép tra cứu trên một triệu phần tử thành chỉ khoảng 20 lần so sánh. Mô thức divide-and-conquer đằng sau nó xuất hiện lại trong cây, cơ sở dữ liệu, và vô số bài toán phỏng vấn. Nắm được yêu cầu khó duy nhất của nó — đầu vào đã sắp xếp — giúp bạn tránh được một lỗi tinh vi kinh điển.