Tìm kiếm nhị phân (binary search) trong Python, bisect
Bài 12/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 8 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Tìm kiếm nhị phân (binary search) là cách tìm trên một list đã sắp xếp: so giá trị cần tìm với phần tử ở giữa, rồi bỏ đi nửa list chắc chắn không chứa nó. Mỗi bước chia đôi phần còn lại, nên tìm trong một triệu mã khách của danh bạ chỉ mất khoảng 20 bước, thay cho một triệu bước của tìm kiếm tuyến tính.
Cần biết trước: tìm kiếm tuyến tính, vòng lặp while và sắp xếp list.
Ý tưởng chia đôi và hàm viết bằng while
Hàm giữ hai chỉ số trai và phai, bao lấy đoạn list còn có thể chứa x. Mỗi vòng lặp lấy chỉ số giữa đoạn và so phần tử ở đó với x. Bằng thì xong. Nhỏ hơn x thì mọi phần tử bên trái nó cũng nhỏ hơn, vì list đã sắp xếp, nên đoạn mới bắt đầu ngay sau giua. Lớn hơn thì đoạn mới kết thúc ngay trước giua.
danh_ba = [102, 117, 125, 140, 158, 163, 171, 189, 194, 205]
def tim_nhi_phan(ds, x):
trai, phai = 0, len(ds) - 1
while trai <= phai:
giua = (trai + phai) // 2
if ds[giua] == x:
return giua
if ds[giua] < x:
trai = giua + 1
else:
phai = giua - 1
return -1
print(tim_nhi_phan(danh_ba, 171), tim_nhi_phan(danh_ba, 150))KẾT QUẢ
6 -1Tìm 171: đoạn đầu là cả list, phần tử giữa ở chỉ số 4 là 158, nhỏ hơn 171, nên đoạn còn lại là từ chỉ số 5 tới 9. Phần tử giữa mới ở chỉ số 7 là 189, lớn hơn, nên đoạn co lại còn chỉ số 5 tới 6. Lần thứ ba gặp 171 ở chỉ số 6. Tìm 150 thì đoạn co dần tới khi trai vượt qua phai: không còn chỗ nào cho 150, hàm trả về -1. Đổi 150 thành 102 rồi chạy lại: in 6 0.
Đếm số bước: O(log n)
Hàm dưới đây đếm số lượt của vòng lặp, cho hai giá trị không có trong list: một nhỏ hơn mọi phần tử, một lớn hơn mọi phần tử.
def so_buoc(ds, x):
trai, phai, buoc = 0, len(ds) - 1, 0
while trai <= phai:
buoc += 1
giua = (trai + phai) // 2
if ds[giua] == x:
return buoc
if ds[giua] < x:
trai = giua + 1
else:
phai = giua - 1
return buoc
for n in [10, 1000, 1_000_000]:
ds = list(range(n))
print(n, so_buoc(ds, -1), so_buoc(ds, n))KẾT QUẢ
10 3 4
1000 9 10
1000000 19 20List dài gấp 100 lần, từ 10 lên 1000 phần tử, chỉ thêm khoảng 6 bước. List một triệu phần tử cần tối đa 20 bước. Số bước là số lần chia đôi n cho tới khi còn một phần tử, tức khoảng log₂ n, và Big O viết là O(log n).
Cái giá phải trả là list phải được sắp xếp trước. Sắp xếp tốn nhiều hơn một lần tìm tuyến tính, nên chỉ đáng khi bạn tìm nhiều lần trên cùng một list, hay khi list vốn đã có thứ tự, như mã khách cấp tăng dần.
Hai lỗi hay gặp khi tự viết
Điều kiện dừng và hai lệnh dời biên phải khớp nhau. Hàm của bài coi phai là chỉ số cuối vẫn còn được xét, nên vòng lặp chạy khi trai <= phai và dời biên tới giua + 1 hoặc giua - 1. Viết phai = giua mà vẫn giữ trai <= phai có thể làm vòng lặp không bao giờ dừng, vì đoạn không co lại. Trên trang, trình chạy tự dừng sau 8 giây và báo hết thời gian chạy. Trên máy, bấm Ctrl+C.
Lỗi thứ hai không nằm ở hàm mà ở dữ liệu đưa vào nó.
Module bisect có sẵn trong Python
Thư viện chuẩn có module bisect, viết sẵn tìm kiếm nhị phân bằng C. bisect_left(ds, x) trả về vị trí đầu tiên có thể chèn x mà list vẫn giữ thứ tự, tức vị trí của phần tử đầu tiên không nhỏ hơn x. bisect_right(ds, x) trả về vị trí ngay sau phần tử cuối bằng x.
from bisect import bisect_left, bisect_right
gio_hen = [8, 8, 9, 9, 9, 10, 11]
print(bisect_left(gio_hen, 9), bisect_right(gio_hen, 9))
dem = bisect_right(gio_hen, 9) - bisect_left(gio_hen, 9)
print(dem, "lịch hẹn lúc 9 giờ")
i = bisect_left(gio_hen, 12)
print(i, i < len(gio_hen) and gio_hen[i] == 12)KẾT QUẢ
2 5
3 lịch hẹn lúc 9 giờ
7 FalseLịch hẹn có ba lịch lúc 9 giờ, từ chỉ số 2 tới 4. Hiệu của hai vị trí là số lịch hẹn lúc 9 giờ. bisect_left() không báo "không có": với 12 nó trả về 7, vị trí ngay sau cuối list. Muốn biết x có trong list không, bạn kiểm thêm phần tử ở vị trí đó như dòng cuối.
insort() chèn một phần tử vào đúng chỗ, để list luôn sắp xếp mà không phải gọi sort() lại. Từ Python 3.10, các hàm của bisect nhận thêm key= như sorted(), để tìm theo một phần của phần tử.
import bisect
gio_hen = [8, 9, 9, 11]
bisect.insort(gio_hen, 10)
bisect.insort(gio_hen, 9)
print(gio_hen)
lich = [("K03", 8), ("K11", 9), ("K07", 11)]
print(bisect.bisect_left(lich, 10, key=lambda hen: hen[1]))KẾT QUẢ
[8, 9, 9, 9, 10, 11]
2Hàm lambda truyền cho key lấy giờ hẹn của từng bộ, nên giá trị cần tìm 10 cũng là một giờ. Kết quả 2 là chỗ chèn một lịch hẹn lúc 10 giờ: sau lịch 9 giờ của K11, trước lịch 11 giờ của K07. Tìm vẫn mất O(log n), nhưng chèn bằng insort() tốn O(n), vì list phải dời các phần tử phía sau sang một chỗ. Cần cả chèn lẫn tìm đều nhanh thì người ta dùng cây nhị phân tìm kiếm tự cân bằng, như cây AVL.
Kiểm tra nhanh
Với hàm
so_buoc()của bài,so_buoc(list(range(10)), 7)trả về gì?124
Với bản dùng
while trai < phaicủa bài,tim_nhi_phan([102, 117], 117)trả về gì?10-1
Hàm
tim_nhi_phan()của bài cho kết quả đúng với mọi giá trị trên những list nào?[102, 117, 125, 140][140, 125, 117, 102]sorted([158, 102, 205])[158, 102, 205]
Với
gio_hen = [8, 8, 9, 9, 9, 10, 11], cặp(bisect_left(gio_hen, 8), bisect_right(gio_hen, 8))bằng gì?(0, 1)(0, 2)(1, 2)
Bài tập
Lịch hẹn đầu tiên của một giờ
Viết hàm vi_tri_dau(ds, x). ds là list giờ hẹn đã sắp xếp tăng dần, có thể trùng nhau. Hàm trả về vị trí (tính từ 0) của lịch hẹn đầu tiên lúc x giờ, hoặc -1 nếu không có lịch nào lúc đó.
Dùng tìm kiếm nhị phân chia đôi bằng hai biên (while hay đệ quy đều được), không dùng module bisect và không cắt list. Trình chấm có lịch 1000 giờ hẹn, trong đó có lịch toàn một giờ, và đếm số phần tử hàm đọc. Gợi ý: gặp phần tử bằng x thì nhớ vị trí rồi vẫn tìm tiếp ở nửa trái.
Ví dụ: vi_tri_dau([8, 8, 9, 9, 9, 10, 11], 9) trả về 2.
Trả về: vị trí, một int.
def vi_tri_dau(ds, x):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Tìm kiếm nhị phân chỉ chạy đúng trên list đã sắp xếp, và mỗi bước bỏ đi một nửa đoạn còn lại.
Số bước tối đa khoảng log₂ n: một triệu phần tử cần khoảng 20 bước, tức O(log n).
Biên
phailà chỉ số cuối còn xét thì vòng lặp chạy khitrai <= phaivà dời biên tớigiua + 1haygiua - 1.bisect_left()vàbisect_right()trả về chỗ chèn bên trái và bên phải các phần tử bằngx, không báo "không có".insort()chèn vào đúng chỗ để list luôn sắp xếp, và từ Python 3.10 các hàm củabisectnhậnkey=.
Câu hỏi thường gặp
Viết tìm kiếm nhị phân bằng đệ quy được không?
Được, theo đúng cách của đệ quy: hàm nhận thêm hai biên trai và phai, so phần tử giữa, rồi gọi lại chính nó với nửa còn lại. Điều kiện dừng là trai > phai. Độ sâu đệ quy chỉ khoảng log₂ n, nên không gặp RecursionError. Bản dùng while vẫn thường được chọn vì ngắn hơn và không tốn tầng gọi hàm.
Thuật toán tìm kiếm nhị phân có chạy trên list giảm dần không?
Hàm của bài thì không, vì nó giả định list tăng dần. Bạn có thể đổi chiều hai phép so sánh. Với bisect từ Python 3.10, dùng key=lambda v: -v và tìm -x: bisect_left([5, 4, 3], -4, key=lambda v: -v) trả về 1.
Vì sao không tính giữa bằng trai + (phai - trai) // 2 như sách Java?
Ở Java hay C, trai + phai có thể vượt giới hạn của kiểu số nguyên, nên người ta viết cách kia. Số nguyên của Python không có giới hạn đó, nên (trai + phai) // 2 luôn đúng.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.