Giải (?) Câu hỏi mục 4 NV1 Bài 7. Lập trình giải bài toán tìm kiếm (trang 117, 118, 119) – SGK Tin học 11 Cánh diều. Tham khảo: Dựa vào kiến thức đã học.
Câu hỏi/Đề bài:
Em hãy thực hiện các yêu cầu sau:
1. Viết mã giả cho thuật toán tìm kiếm nhị phân.
2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.
3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.
Hướng dẫn:
Dựa vào kiến thức đã học.
Lời giải:
1) Bắt đầu: Phạm vi tìm kiếm là dãy ban đầu
Lặp khi Vẫn còn Phạm vi tìm kiếm:
Xác định phần tử am giữa Phạm vi tìm kiếm
Nếu x=am:
Thông báo tìm thấy x ở vị trí m và kết thúc
Ngược lại:
Loại bỏ nửa dãy chắc chắn không chứa x
Phạm vi tìm kiếm là nửa dãy còn lại
Hết nhánh
Hết lặp
Thông báo không tìm thấy x và kết thúc.
2) Số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân:
Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2 mũ k. Kết thúc khi 2 mũ k sấp xỉ n.
3) Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân O(n).