Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau:
a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một số khác nhau. Sắp xếp các thẻ số thành một dãy trên mặt bàn theo thứ tự giá trị tăng dần của số ghi trên thẻ. Đặt úp mặt ghi số để không nhìn thấy số ghi trên các thẻ.
b) Em đề nghị bạn thực hiện thuật toán tìm kiếm nhị phân để tìm một số do em đưa ra.
c) Hoán đổi vai trò, em thực hiện tìm kiếm theo đề nghị của bạn.
Chuẩn bị 10 thẻ được đánh thứ từ từ A, B, C, D, E, F, G, H, K, L và sau thẻ đánh số tương ứng 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 xếp sắp theo thứ tự tăng dần.
a) Thẻ số tăng dần: Tìm số 8
b)
Gọi số cần tìm là x = 8.
Bước 1. Lật thẻ ở vị trí E (E = 5).
Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (8 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).
Bước 3. Lật thẻ vị trí H (H = 8).
Bước 4. So sánh số thấy vị trí H bằng với kết quả cần tìm. Kết quả tìm thấy số 8 trong dãy ở vị trí H và kết thúc quá trình tìm kiếm.
c) Thay đổi vai trò
Gọi số cần tìm là x = 10.
Bước 1. Lật thẻ ở vị trí E (E = 5).
Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (10 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).
Bước 3. Lật thẻ vị trí H (H = 8).
Bước 4. So sánh số thấy vị trí H khác vị trí cần tìm (10 > 8). Nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm K, L).
Bước 5. Ta lật ngẫu nhiên vị trí K hoặc L.
+ TH1: Lật thẻ vị trí K: So sánh số thấy vị trí K khác vị trí cần tìm (10 > 9). Tiếp theo ta lật thẻ còn lại, so sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.
+ TH2: Lật thẻ vị trí L: So sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.