Câu II.4 · 28/28
Đề bài
Dùng tìm nhị phân trên danh sách tăng; count đếm số lần xét phần tử giữa:
```python
a = [3, 6, 9, 12, 15, 18, 21]
x = 22
left, right = 0, len(a) - 1
count = 0
while left <= right:
mid = (left + right) // 2
count += 1
if a[mid] == x:
break
elif a[mid] < x:
left = mid + 1
else:
right = mid - 1
print(count)
```
- AĐúngcount bằng 3.
- BĐúngNếu tìm tuần tự từ đầu đến cuối và chỉ dừng khi bằng x thì cần xét 7 phần tử.
- CSaiKhông tìm thấy x thì tìm nhị phân bắt buộc phải đọc mọi phần tử.
- DSaiCó thể dùng số lượt 3 để kết luận mọi danh sách dài bao nhiêu cũng chỉ cần 3 lượt.
Hướng dẫn giải
**Đáp án**:
a) Đúng
b) Đúng
c) Sai
d) Sai
**Giải thích**:
a) Các giá trị được xét là 12, 18 và 21.
b) 22 không có nên cách tuần tự mô tả phải xét đủ 7 phần tử.
c) Nhờ thứ tự, nó loại được các đoạn mà không đọc từng phần tử.
d) Số lượt phụ thuộc kích thước và đường tìm kiếm, không cố định bằng 3.