Tuần 21 — Thuật toán tìm kiếm nhị phân
Tin học Lớp 10 · 6 câu hỏi có lời giải
Câu 1.Tìm kiếm nhị phân yêu cầu?
- A.Mảng bất kỳ
- B.Mảng đã sắp xếp
- C.Mảng rỗng
- D.Mảng có 1 phần tử
Xem đáp án
Đáp án: B. Mảng đã sắp xếp
Binary search yêu cầu mảng phải được sắp xếp.
Câu 2.Tìm nhị phân hoạt động bằng cách?
- A.Đảo ngược
- B.Chia đôi liên tục, so sánh giữa
- C.Duyệt từ đầu
- D.Sắp xếp lại
Xem đáp án
Đáp án: B. Chia đôi liên tục, so sánh giữa
Mỗi bước so sánh phần tử giữa, loại bỏ nửa không chứa target.
Câu 3.Độ phức tạp tìm nhị phân?
- A.O(n) — như tìm tuyến tính
- B.O(log n)
- C.O(1) — truy cập trực tiếp
- D.O(n²) — như bubble sort
Xem đáp án
Đáp án: B. O(log n)
Binary search: O(log n) - rất nhanh với mảng lớn.
Câu 4.Tìm số 7 trong [1,3,5,7,9,11] bằng nhị phân?
- A.So với 5 (giữa) → so với 9 → tìm thấy 7
- B.Bắt đầu từ cuối
- C.Đảo ngược
- D.Duyệt từng phần tử
Xem đáp án
Đáp án: A. So với 5 (giữa) → so với 9 → tìm thấy 7
Mid index 2 (val 5), 7 > 5 → tìm bên phải; mid mới là index 4 (val 9), 7 < 9 → bên trái; thấy 7.
Câu 5.Python có hàm thư viện tìm nhị phân?
- A.find (tìm chuỗi con)
- B.locate
- C.bisect
- D.search
Xem đáp án
Đáp án: C. bisect
Module bisect cung cấp bisect_left, bisect_right cho tìm nhị phân.
Câu 6.Nếu không tìm thấy, tìm nhị phân kết thúc khi?
- A.left == right
- B.left < 0
- C.Không bao giờ
- D.left > right
Xem đáp án
Đáp án: D. left > right
Vòng lặp dừng khi left > right (khoảng tìm rỗng).