Tìm kiếm nhị phân

Tìm kiếm nhị phân giống cách bạn tra từ điển: mở ở giữa, xem từ cần tìm nằm trước hay sau, rồi lặp lại với nửa đó. Trên danh sách đã sắp xếp, nó tìm được bất kỳ giá trị nào trong một triệu giá trị với nhiều nhất 20 phép so sánh.

Một hàng cột đã sắp xếp, cột giữa được làm nổi bật, một nửa hàng mờ đi, và một đường nét đứt ở độ cao của giá trị cần tìm
Một hàng cột đã sắp xếp, cột giữa được làm nổi bật, một nửa hàng mờ đi, và một đường nét đứt ở độ cao của giá trị cần tìm

Ý tưởng

Trong danh sách đã sắp xếp, một phép so sánh cho bạn biết nhiều hơn việc đã tìm thấy hay chưa: nó cho biết giá trị cần tìm nằm ở phía nào. So sánh giá trị cần tìm với giá trị ở giữa. Nếu bằng nhau là xong. Nếu giá trị giữa nhỏ hơn, mọi giá trị trước nó cũng nhỏ hơn, nên giá trị cần tìm chỉ có thể nằm sau nó. Nếu lớn hơn, giá trị cần tìm chỉ có thể nằm trước nó. Chỉ giữ lại nửa đó và lặp lại.

Một ví dụ

Tìm 23 trong 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Giá trị giữa là 16, nhỏ hơn, nên chỉ còn 23 đến 91. Giá trị giữa của chúng là 56, lớn hơn, nên chỉ còn 23 và 38. Giá trị giữa của chúng là 23: tìm thấy ở vị trí 6 sau 3 phép so sánh, trong khi tìm kiếm tuyến tính cần 6. Tìm 40 trong cùng danh sách sẽ so sánh 16, 56, 23 và 38, sau đó không còn gì: 4 phép so sánh để biết 40 không có, so với 10 của tìm kiếm tuyến tính.

Chia đôi giảm rất nhanh

Sau một phép so sánh còn nhiều nhất một nửa danh sách, sau hai còn một phần tư, sau k còn nhiều nhất khoảng n/2ᵏ. Việc tìm kiếm dừng khi không còn gì, nên cần nhiều nhất ⌊log₂ n⌋ + 1 phép so sánh: 6 cho 40 giá trị, 10 cho 1.000, 20 cho một triệu và 30 cho một tỷ. Gấp đôi danh sách chỉ thêm một phép so sánh. Điều này được viết là O(log n).

Dễ mô tả, khó viết đúng

John Mauchly mô tả tìm kiếm nhị phân năm 1946, nhưng theo Donald Knuth, phiên bản đầu tiên chạy đúng với mọi độ dài danh sách mãi đến năm 1962 mới được công bố. Sau này Jon Bentley nhận thấy chỉ khoảng một phần mười lập trình viên chuyên nghiệp viết đúng: điều kiện kết thúc và việc cộng hay trừ một khi chia đôi rất dễ sai. Năm 2006, Joshua Bloch chỉ ra rằng cách tìm giữa phổ biến, (low + high) / 2, có thể bị tràn số với danh sách rất dài, một lỗi đã nằm trong thư viện Java nhiều năm. Viết low + (high − low) / 2, như ứng dụng này làm, sẽ tránh được lỗi đó.

John Mauchly (thứ năm từ trái sang) cùng các phụ trách khác của ENIAC trước cỗ máy, trong một bức ảnh của Quân đội Hoa Kỳ. Mauchly mô tả tìm kiếm nhị phân vào năm 1946.
John Mauchly (thứ năm từ trái sang) cùng các phụ trách khác của ENIAC trước cỗ máy, trong một bức ảnh của Quân đội Hoa Kỳ. Mauchly mô tả tìm kiếm nhị phân vào năm 1946.

Biến thể và ứng dụng

Khi có giá trị trùng, tìm kiếm nhị phân tìm thấy một trong các giá trị khớp; các phiên bản tiếp tục sang trái hoặc phải sẽ tìm thấy giá trị đầu tiên hoặc cuối cùng, hoặc vị trí mà một giá trị không có sẽ được chèn vào. Cùng ý tưởng chia đôi giúp tìm nghiệm của phương trình (phương pháp chia đôi), phiên bản mà lỗi xuất hiện lần đầu (git bisect), và lời giải của nhiều bài toán tối ưu. Cây tìm kiếm nhị phân lưu dữ liệu sao cho mỗi lần tra cứu đều đi theo cùng một đường chia đôi.

Khám phá

Mở ứng dụng, chọn một giá trị ở mục Tìm, rồi nhấn Bước. Phần tô bóng là nơi giá trị cần tìm vẫn có thể nằm; giá trị giữa được làm nổi bật, còn nửa bị loại mờ đi. Các ô cho biết còn bao nhiêu giá trị có khả năng và tìm kiếm tuyến tính cần bao nhiêu phép so sánh cho cùng giá trị đó. Hãy tìm một giá trị không có, hoặc dùng 40 cột, để thấy khoảng cách tăng lên.

Câu hỏi thường gặp

Độ phức tạp thời gian của tìm kiếm nhị phân là bao nhiêu?

O(log n): nhiều nhất ⌊log₂ n⌋ + 1 phép so sánh cho n giá trị. Trường hợp tốt nhất là một phép so sánh, khi giá trị cần tìm nằm ngay giữa. Phiên bản lặp chỉ cần thêm O(1) bộ nhớ.

Tìm kiếm nhị phân khác tìm kiếm tuyến tính thế nào?

Tìm kiếm tuyến tính kiểm tra lần lượt từng giá trị và dùng được với mọi danh sách, nhưng có thể cần n phép so sánh. Tìm kiếm nhị phân chỉ dùng được với danh sách đã sắp xếp, nhưng mỗi phép so sánh loại bỏ một nửa phần còn lại, nên chỉ cần khoảng log₂ n.

Có đáng sắp xếp danh sách chỉ để dùng tìm kiếm nhị phân không?

Chỉ khi bạn tìm trong đó nhiều lần. Sắp xếp mất khoảng n log n bước, nhiều hơn một lần tìm kiếm tuyến tính. Khi danh sách đã sắp xếp, mọi lần tìm sau đó đều rất ít tốn kém.

Tìm kiếm nhị phân có dùng được cho thứ khác ngoài danh sách không?

Có, với bất cứ thứ gì mà một phép thử cho biết bạn đang ở phía nào của đáp án: một khoảng số, các phiên bản của một chương trình, hoặc các lần đoán trong trò chơi đoán lớn hơn hay nhỏ hơn.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử tìm kiếm nhị phân