(2 điểm) Cho dãy số {5, 11, 18, 39, 41, 52, 63, 70}. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm nhị phân để tìm số 60 trong dãy.

Tìm kiếm x = 60.

{5, 11, 18, 39, 41, 52, 63, 70}.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy.

Vì x > a₄ nên có nửa đầu dãy chắc chắn không chứa x = 60 tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi cần tìm tiếp theo là dãy con từ a₅ đến a₈.

Chia đôi lần 2: lấy a₆ là số có vị trí giữa dãy còn lại.

Vì x > a₆ nên nửa đầu dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a₇ đến a₈.

Chia đôi lần 3: lấy a₇ là số có vị trí giữa dãy còn lại.

Vì x < a7 nên nửa sau dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con một phần tử là a7.

Chỉ còn một phần tử, không chia đôi nữa, so sánh thấy x khác a7. Kết luận: Không tìm thấy.