Giải SBT Tin học 7 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ó đáp án

Dãy xuất phát:

1) Số phải tìm là x (x = 39). Các bước thực hiện tìm kiếm:

2) Số phải tìm là x (x = 60). Các bước thực hiện tìm kiếm:

Các bước thực hiện như sau:

Các bước thực hiện như sau:

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$_{1}$ đến a$_{8}$. Lấy a$_{4}$ là số có vị trí giữa dãy. Vì x = a$_{4}$ 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$_{1}$ đến a$_{8}$. Lấy a$_{4}$ là số có vị trí giữa dãy.

Vì x > a$_{4}$ 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$_{5}$ đến a$_{8}$.

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

Vì x > a$_{6}$ 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$_{7}$ đến a$_{8}$.

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

Vì x < a$_{7}$ 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$_{7}$.

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