Điều kiện để áp dụng thuật toán nhị phân là:
A. Không có điều kiện.
B. Dãy đã được sắp xếp tăng dần.
C. Dãy đã được sắp xếp giảm dần.
D. Cả C và B
Giải bởi Vietjack
Đáp án đúng là: D
Điều kiện để áp dụng thuật toán nhị phân là: Dãy đã được sắp xếp tăng dần hoặc giảm dần.
Sử dụng kiến thức dưới đây:
Thuật toán tìm kiếm nhị phân
- Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.
- Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.
Hình 2.1: Một mô tả của thuật toán tìm kiếm nhị phân
Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử đứng giữa dãy là am để so sánh với x. Nếu am = x thì kết thúc. Trái lại, sẽ có hai trường hợp:
- Nếu am < x thì chắc chắn không có x trong nửa đầu của dãy.
- Nếu x < am thì chắc chắn không có x trong nửa sau của dãy.
Lặp lại theo cách như thế cho đến khi hoặc tìm thấy hoặc độ dài dãy phạm vi tìm kiếm là bằng 0.
Tham khảo thêm một số tài liệu liên quan:
Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?
Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi:
Cho dãy số 0, 1, 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy” có phần tử giữa là:
Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, cho kết quả là:
Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân:
Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, có phạm vi tìm kiếm là:
Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa đầu của dãy:
Để tìm một số trong dãy đã được sắp xếp tăng dần, thuật toán tìm kiếm nhanh nhất là:
Cho dãy số 0, 1, 2, 4, 6, 8, 9. Bài toán “Tìm số x=4 trong dãy” có số lần lặp là:
Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa sau của dãy:
Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
© 2021 Vietjack. All Rights Reserved.
