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.
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
Đá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.
Tham gia Cộng đồng Lazi trên các mạng xã hội | |
Fanpage: | https://www.fb.com/lazi.vn |
Group: | https://www.fb.com/groups/lazi.vn |
Kênh FB: | https://m.me/j/AbY8WMG2VhCvgIcB |
LaziGo: | https://go.lazi.vn/join/lazigo |
Discord: | https://discord.gg/4vkBe6wJuU |
Youtube: | https://www.youtube.com/@lazi-vn |
Tiktok: | https://www.tiktok.com/@lazi.vn |
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |