Câu 4

Cho đoạn chương trình sau viết bằng Python và ngôn ngữ C++ dùng để tìm kiếm một số nguyên X trong danh sách A (đã được sắp xếp tăng dần): Một bạn học sinh sau khi đọc đoạn code đã đưa ra các nhận định sau:

Phát biểu

Đúng

Sai

Trong vòng lặp while, biến m luôn bằng chỉ số của phần tử nằm giữa đoạn chỉ số từ L đến R trong danh sách A.

Hàm tim_kiem_nhi_phan sẽ trả về giá trị 0 nếu phần tử cần tìm không tồn tại trong danh sách A.

Nếu X không có trong danh sách A, thì sau mỗi lần lặp của vòng lặp while, số lượng phần tử còn lại trong đoạn chỉ số từ L đến R giảm ít nhất một nửa.

Với danh sách A gồm 1000 phần tử đã sắp xếp tăng dần và X không có trong danh sách, vòng lặp while có thể thực hiện hơn 15 lần trước khi dừng.

Giải thích câu 4

😎 Cùng DOL xem qua cách giải câu này nhé!

✅ Đáp án: Đúng

🔎 Lí do:

Câu phát biểu này khá rõ ràng.
- Ý cần kiểm tra là: trong mỗi lần lặp của vòng while, biến `m` có đúng là chỉ số nằm giữa đoạn từ `L` đến `R` hay không.
Đoạn chương trình cho biết:
- Trong Python: `m = (L + R) // 2`
- Trong C++: `int m = (L + R) / 2;` => Cả hai cách viết đều tính chỉ số giữa của đoạn đang xét từ L đến R.
Vì L là chỉ số đầu đoạn, R là chỉ số cuối đoạn, nên giá trị m được tính từ trung điểm của hai chỉ số này. Đây chính là vị trí ở giữa đoạn chỉ số từ L đến R dùng trong thuật toán tìm kiếm nhị phân.

=> Vì vậy, phát biểu đúng.