Câu hỏi/bài tập:
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.
Dựa vào kiến thức đã học.
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
Advertisements (Quảng cáo)
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).