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 kiếm x trong dãy

Giải SBT Tin học 7 Cánh diều Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

Câu F22 trang 39 SBT Tin học 7: 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 kiếm x trong dãy.

1) x = 39

2) x = 60

Trả lời:

1) Số phải tìm là x = 39:

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 đã tìm thấy x = 39 tại vị trí thứ tư.

2) Số phải tìm là x = 60:

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 = 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 (có nền màu xám nhạt) 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 < a₇ nên nửa sau dãy (có nền màu xám nhạt) 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à a₇.

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

Xem thêm các bài giải sách bài tập Tin học 7 Cánh diều hay, chi tiết khác:

Câu F19 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm tuần tự áp dụng cho dãy số... 

Câu F20 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số... 

Câu F21 trang 39 SBT Tin học 7: Hãy trình bày diễn biến từng bước của thuật toán sắp xếp nổi bọt áp dụng cho dãy số {11, 70, 18...  

Câu F22 trang 39 SBT Tin học 7: 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 kiếm x trong dãy...