Cho mảng đã sắp xếp [2, 5, 8, 12, 16, 23]. Khi sử dụng thuật toán tìm kiếm nhị phân để tìm

Câu hỏi số 958925:

Vận dụng

Cho mảng đã sắp xếp [2, 5, 8, 12, 16, 23]. Khi sử dụng thuật toán tìm kiếm nhị phân để tìm giá trị x = 12, cần bao nhiêu lần so sánh?

A. 1

B. 3

C. 2

D. 4

Đáp án đúng là: B

Quảng cáo

Xem lời giải

Câu hỏi:958925

Phương pháp giải

Thuật toán tìm kiếm nhị phân chia đôi phạm vi tìm kiếm tại mỗi bước bằng cách so sánh giá trị cần tìm với phần tử ở giữa (chỉ số giữa mid = (low + high) // 2).

Giải chi tiết

Mảng có 6 phần tử, chỉ số từ 0 đến 5. Cần tìm x = 12.

Lần 1: $\left. low = 0,high = 5\rightarrow mid = (0 + 5)//2 = 2 \right.$. Phần tử a[2] = 8. Vì 8 < 12, ta tìm ở nửa bên phải (chỉ số 3 đến 5).

Lần 2: $\left. low = 3,high = 5\rightarrow mid = (3 + 5)//2 = 4 \right.$. Phần tử a[4] = 16. Vì 16 > 12, ta tìm ở nửa bên trái (chỉ số 3 đến 3).

Lần 3: $\left. low = 3,high = 3\rightarrow mid = (3 + 3)//2 = 3 \right.$. Phần tử a[3] = 12. Vì 12 = 12, tìm thấy giá trị.

Đáp án cần chọn là: B

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.