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

Câu hỏi: 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 

Lời giải: 

Các em tham khảo hướng dẫn sau:

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.

- Thẻ số tăng dần: Tìm số 8

Hình 2: Thẻ số tăng dần

- 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.

- 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.