Giả sử cần sử dụng thuật toán tìm kiếm nhị phân để tìm ra số 10 trong dãy số sau: A= [1, 3, 10, 12, 14, 15, 16]

Giải SBT Tin học 11 Bài 20: Thực hành bài toán tìm kiếm

Câu 20.6 trang 68 SBT Tin học 11: Giả sử cần sử dụng thuật toán tìm kiếm nhị phân để tìm ra số “10” trong dãy số sau:

A= [1, 3, 10, 12, 14, 15, 16].

Hỏi có bao nhiêu phép so sánh cần được thực hiện?>

A. 2.

B. 3.

C. 4.

D. Thuật toán không tìm thấy số cần tìm.

Lời giải:

Đáp án đúng là: B. Thuật toán tìm kiếm nhị phân được thực hiện như sau:

Bước 1: Kiểm tra số chính giữa là số “12”, lớn hơn 10 nên số cần tìm nằm ở nửa trái của dãy. Dãy cần tìm kiếm tiếp là [1, 3, 10].

Bước 2: Kiểm tra số chính giữa của dãy thu gọn là số “3”, nhỏ hơn 10 nên số cần tìm nằm ở nửa phải của dãy. Dãy cần tìm kiếm tiếp là [10].

Bước 3: Kiểm tra số chính giữa của dãy thu gọn là số “10”, bằng 10. Kết luận tìm ra số cần tìm và kết thúc chương trình.

Như vậy, có 3 phép so sánh cần thực hiện.