Tìm kiếm nhị phân — Thuật toán, độ phức tạp thời gian & mã

Tìm kiếm nhị phân là một cách nhanh để tìm một giá trị mục tiêu trong danh sách đã sắp xếp. Bạn kiểm tra phần tử ở giữa, loại bỏ một nửa các giá trị còn lại, rồi lặp lại. Nếu danh sách chưa được sắp xếp, logic đó không còn đúng.

Với danh sách tăng dần, quy tắc rất đơn giản: nếu giá trị ở giữa nhỏ hơn mục tiêu thì tìm sang phải; nếu lớn hơn thì tìm sang trái. Vì phạm vi liên tục thu hẹp khoảng một nửa, tìm kiếm nhị phân chạy trong thời gian $O(\log n)$.

Cách tìm kiếm nhị phân hoạt động trên danh sách đã sắp xếp

Dùng danh sách đã sắp xếp sau:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Giả sử giá trị cần tìm là $31$.

Bắt đầu với toàn bộ phạm vi. Giá trị ở giữa là $24$. Vì $31 > 24$, mọi phần tử bên trái của $24$ đều có thể bị loại bỏ, nên việc tìm kiếm tiếp tục trong

$$[31, 39, 45, 52]$$

Bây giờ giá trị ở giữa là $39$. Vì $31 < 39$, mọi phần tử bên phải của $39$ đều có thể bị loại bỏ, nên phạm vi trở thành

$$[31]$$

Lúc này giá trị ở giữa là $31$, nên việc tìm kiếm dừng lại. Ý tưởng quan trọng không chỉ là đã tìm thấy mục tiêu. Chỉ trong hai lần so sánh, phạm vi ứng viên đã giảm từ $9$ giá trị xuống còn $1$.

Vì sao tìm kiếm nhị phân là $O(\log n)$

Mỗi lần so sánh loại bỏ khoảng một nửa số ứng viên còn lại. Sau một bước, còn khoảng $n/2$ phần tử. Sau hai bước, còn khoảng $n/4$ phần tử. Sau $k$ bước, kích thước còn lại xấp xỉ

$$\frac{n}{2^k}$$

Việc tìm kiếm kết thúc khi lượng đó xấp xỉ $1$, nên số bước thỏa mãn

$$2^k \approx n$$

Lấy $\log_2$ hai vế, ta được

$$k \approx \log_2 n$$

Đó là lý do tìm kiếm nhị phân mở rộng rất tốt khi dữ liệu lớn lên. Tìm kiếm tuyến tính có thể cần tới $n$ lần kiểm tra, nhưng tìm kiếm nhị phân chỉ cần đủ số lần kiểm tra để liên tục chia đôi phạm vi.

Ví dụ mã tìm kiếm nhị phân

Đây là một phiên bản lặp tiêu chuẩn trong Python: