Luyện tập trang 83 Tin học lớp 7: Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phần để tìm kiếm x=60 trong dãy trên.
Có thể trình bày thông tin mô tả dưới dạng bảng như bài học.
Tìm x = 60:
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
|
Xuất phát |
5 |
11 |
18 |
39 |
41 |
52 |
63 |
70 |
|
Bước 1 |
|
|
|
39 |
|
52 |
|
|
|
Bước 2 |
|
|
|
|
|
52 |
|
|
- Chia đôi lần 1. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 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ảu dãy. Phạm vi tìm kiếm từ A5 đến A8.
- Chia đôi lần 2. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 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. Phạm vi tìm kiếm từ A7 đến A8.
- Chia đôi lần 3. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x
Kết thúc thuật toán: Không tìm thấy x có trong dãy.
Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác: