Gợi ý: Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm trên danh sách đã được sắp xếp. Một số ví dụ về danh sách như sau: danh sách học sinh trong lớp, danh mục sách trong thư viện, danh mục hàng hóa, danh mục thiết bị,… Trước tiên em lập danh sách và sắp xếp danh sách. Sau đó xác định giá trị cần tìm. Cuối cùng thực hiện thuật toán tìm kiếm nhị phân để tìm giá trị trong danh sách đã được sắp xếp.
Trả lời:
Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3
Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.
Gói VIP thi online tại VietJack (chỉ 200k/1 năm học), luyện tập gần 1 triệu câu hỏi có đáp án chi tiết
Điều kiện lặp của thuật toán tìm kiếm nhị phân là gì?
A. Chưa tìm thấy phần tử cần tìm.
B. Chưa hết danh sách.
C. Chưa tìm thấy phần tử cần tìm hoặc chưa hết danh sách.
D. Chưa tìm thấy phần tử cần tìm và chưa hết danh sách.
Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước để thông báo không tìm thấy số 10 trong danh sách [2, 5, 8, 11, 14, 17] ?
A. 2 B. 3 C. 4 D. 5
Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greendland, Germany
Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.
Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy Thailand trong danh sách tên các nước sau:
Brunei, Campodia, Laos, Myanmar, Singpore, Thailand, Vietnam
A. 1 B. 2 C. 3 D. 4