(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ố 63 trong dãy.

Tìm kiếm x = 63.

{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 (có nền màu xám nhạt) chắc chắn không chứa x = 63, 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 (có nền màu xám nhạt) chắc chắn không chứa x = 63, 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 = a₇= 63 nên thông báo tìm thấy số 63.