Tìm kiếm nhị phân và tìm kiếm tuần tự thì thuật toán nào nhanh hơn?
Giải bởi Vietjack
Đáp án đúng là: A
Tìm kiếm nhị phân nhanh hơn thuật toán tìm kiếm tuần tự vì sau mỗi bước lặp thì phạm vi tìm kiếm thu hẹp 1 nửa so với bước trước.
Gói VIP thi online tại VietJack (chỉ 400k/1 năm học), luyện tập gần 1 triệu câu hỏi có đáp án chi tiết
Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy sắp xếp diễn biến từng bước kìm kiếm nhị phần để tìm kiếm x=60 trong dãy trên.
Tìm x = 60:
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
|
Xuất phát |
5 |
11 |
18 |
39 |
41 |
52 |
63 |
70 |
|
Bước 1 |
|
|
|
39 |
41 |
52 |
63 |
70 |
|
Bước 2 |
|
|
|
|
|
52 |
63 |
70 |
|
Bước 3 |
|
|
|
|
|
|
63 |
|
1. Kết thúc thuật toán: Không tìm thấy x có trong dãy.
2. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x<A7 nên nửa sau chắc chắn không chứa x.
3. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.
4. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A5 đến A8.
Phát biểu đúng nhất về “Thuật toán tìm kiếm nhị phân” (tìm x trong dãy số đã được sắp thứ tự không giảm)?
Lấy phần tử đứng giữa dãy để so sánh với x, nếu phần tử đó chính là x thì kết luận gì?
Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là gì?
