Giả sử cần sử dụng thuật toán tìm kiếm nhị phân để tìm ra số 10

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:

Sách bài tập Tin học 11 Bài 20: Thực hành bài toán tìm kiếm - Kết nối tri thức

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.

Lời giải sách bài tập Tin học 11 Bài 20: Thực hành bài toán tìm kiếm hay khác: