Tìm kiếm nhị phân trong Python
Tìm một giá trị trong list một triệu phần tử đã sắp xếp chỉ với khoảng 20 bước, nhờ chia đôi phạm vi tìm sau mỗi lần so sánh.
- Các chỉ số low, middle và high
- Vì sao list phải được sắp xếp
- Module bisect
Mỗi bước bỏ đi một nửa
Vấn đề
Tìm một giá trị trong list một triệu phần tử bằng cách xem từng phần tử có thể mất tới một triệu lần so sánh. Khi list đã được sắp xếp, bạn có cách nhanh hơn nhiều: chừng 20 lần so sánh là đủ, vì mỗi lần kiểm tra loại được một nửa phần còn lại.
Hình dung đời thường
Tìm kiếm nhị phân (binary search) chính là cách bạn tra một từ trong cuốn từ điển giấy. Bạn mở ở giữa, xem từ cần tìm đứng trước hay sau trang đó, rồi bỏ đi nửa không thể chứa nó. Lặp lại với nửa còn lại cho tới khi gặp đúng từ.
low, high = 0, len(values) - 1📖 Những trang còn phải tìmmiddle = (low + high) // 2👆 Mở ở giữalow = middle + 1➡️ Từ cần tìm nằm sau: bỏ nửa đầuhigh = middle - 1⬅️ Từ cần tìm nằm trước: bỏ nửa sauTìm kiếm nhị phân tìm một giá trị trong list đã sắp xếp bằng cách liên tục so nó với phần tử ở giữa và bỏ đi nửa không thể chứa nó, mất khoảng O(log n) bước.
Những điểm quan trọng
lowvàhighđánh dấu phần list vẫn còn có thể chứa giá trị cần tìm.middle = (low + high) // 2chọn vị trí ở giữa phần đó.- Nếu
values[middle] < target, giá trị cần tìm nằm bên phải nênlow = middle + 1; ngược lạihigh = middle - 1. while low <= high:dừng khi khoảng tìm kiếm rỗng, và hàm trả về-1nghĩa là không tìm thấy.- Với 17, quá trình tìm xem 12, rồi 25, rồi 17: ba lần so sánh thay vì bốn.
Khi nào nên sử dụng?
- Tìm trong dữ liệu lớn đã sắp xếp: mã số, từ điển, log đã sắp theo thời gian.
- Tìm vị trí chèn một giá trị để list vẫn giữ thứ tự.
- Trò chơi đoán số và mọi bài toán có thể thu hẹp đáp án bằng cách hỏi cao hơn hay thấp hơn.
Khi nào chưa cần
- Dữ liệu chưa sắp xếp: sắp xếp chỉ để tìm một lần còn tốn hơn tìm tuần tự.
- List nhỏ hoặc chỉ tìm một lần:
inhay dictionary đơn giản hơn; tra cứu theo khóa nhiều lần thì dict hoặc set còn nhanh hơn.
Mô phỏng Tìm kiếm nhị phân (binary search) trong Python
O(log n)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
Kết quả khi chạy
3
Giải thích code
Hai biến low và high xác định phạm vi tìm kiếm còn lại. Nếu phần tử ở giữa nhỏ hơn giá trị cần tìm, thuật toán bỏ nửa bên trái bằng cách đặt low = middle + 1, ngược lại thì bỏ nửa bên phải. Độ phức tạp thời gian là O(log n), với điều kiện danh sách đầu vào bắt buộc phải được sắp xếp trước.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Dùng < thay vì <= trong vòng lặp
Với low < high, giá trị nằm ở vị trí cuối cùng còn lại sẽ không bao giờ được kiểm tra.
while low < high:
while low <= high:
Không bước qua vị trí giữa
Gán low = middle có thể khiến vòng lặp xét mãi cùng một vị trí giữa.
low = middle
low = middle + 1
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Thời Gian Sản Xuất Nhà Máy Tìm thời điểm sớm nhất mà các máy chạy song song có thể hoàn thành số lượng sản phẩm mục tiêu. Trung bình
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Khó