Tin học · Tìm kiếm nhị phân
Làm sao tìm một cái tên giữa một triệu cái tên trong 20 bước?
Bạn sẽ thấy gì
Một cuốn danh bạ có một triệu cái tên, xếp theo thứ tự chữ cái. Kiểm tra từng cái một có thể mất một triệu lần nhìn. Có cách nào tốt hơn không? Mở ngay chính giữa. Cái tên bạn cần nằm phía sau, nên cả nửa đầu bị loại. Còn lại nửa triệu. Mở chính giữa phần còn lại, và chia đôi lần nữa. Rồi lại chia. Mỗi lần nhìn loại bỏ một nửa phần còn lại. Hai mươi lần chia đôi đưa một triệu xuống còn một, vì hai mũ hai mươi chỉ hơn một triệu một chút. Một tỷ cái tên? Chỉ thêm mười lần nhìn.
