Thuật toán tìm kiếm nhị phân
Bài học dùng danh sách đã sắp xếp để tìm theo vị trí giữa và thu hẹp phạm vi còn một nửa.
Hiểu bài
Tìm kiếm nhị phân chỉ áp dụng khi danh sách đã được sắp xếp. Ban đầu, vùng tìm kiếm là toàn bộ danh sách. Thuật toán xác định vị trí giữa, so sánh giá trị cần tìm với phần tử giữa, rồi giữ lại một nửa phù hợp. Nếu bằng nhau thì kết luận tìm thấy; nếu vùng tìm kiếm không còn phần tử thì kết luận không tìm thấy.
Trong danh sách tên đã xếp theo bảng chữ cái gồm An, Bình, Hoà, Liên, Mai, Phương, Trang, Trúc, Tước, khi tìm “Trúc”, trước hết so sánh với “Mai” ở vị trí 5. Vì “Trúc” đứng sau “Mai”, bỏ nửa đầu. Tiếp theo so sánh với “Trang” ở vị trí 7 và tiếp tục giữ nửa sau.
Nhờ danh sách đã sắp xếp, sau mỗi lần so sánh phạm vi tìm kiếm giảm còn khoảng một nửa. Trong ví dụ chín phần tử không có giá trị cần tìm, SGK nêu tìm kiếm tuần tự cần 9 bước lặp còn tìm kiếm nhị phân chỉ cần 4 bước.
Danh sách khách hàng đã sắp xếp SGK trang 74