Sắp xếp là điều kiện để bỏ nửa dãy
Xét `a = [3, 7, 11, 15, 19, 23, 27]` đã tăng dần và cần tìm 23. Phạm vi ban đầu là chỉ số 0–6. Phần tử giữa ở chỉ số `(0+6)//2=3` có giá trị 15. Vì 23 lớn hơn 15, mọi phần tử ở **bên trái và tại giữa** đều nhỏ hơn 23, nên chỉ cần xét phạm vi 4–6. Giữa phạm vi mới là chỉ số 5, có giá trị 23: tìm thấy sau hai lần so sánh.
Nếu dãy chưa sắp xếp, so sánh ở giữa không cho phép bỏ cả một nửa. Chẳng hạn với `[9, 1, 5]`, tìm 9 bằng cách bỏ nửa trái sau khi thấy 1 ở giữa sẽ trả sai dù 9 nằm ở đầu.
Mỗi bước làm phạm vi ngắn hơn
```python
def tim_nhi_phan_tang(a, k):
left = 0
right = len(a) - 1
while left <= right:
mid = (left + right) // 2
if a[mid] == k:
return mid
if a[mid] < k:
left = mid + 1
else:
right = mid - 1
return -1
print(tim_nhi_phan_tang([3, 7, 11, 15, 19, 23, 27], 23))
print(tim_nhi_phan_tang([3, 7, 11, 15, 19, 23, 27], 20))
```
Kết quả là `5` và `-1`. Ở mỗi lần chưa khớp, bỏ luôn `mid` vì đã biết `a[mid]` khác `k`; `left=mid+1` hoặc `right=mid-1` làm phạm vi nhỏ đi. Khi `left>right`, phạm vi rỗng nên không thấy. Với dãy rỗng, `right=-1` và vòng lặp không chạy. Hàm này **chỉ dùng khi dãy đã sắp xếp tăng**; mã không tự kiểm hoặc tự sắp xếp dữ liệu.
Bài luyện
Dãy tăng `[3,7,11,15,19,23,27]`, tìm 23: sau khi xét phần tử giữa 15, phạm vi nào còn cần tìm?
Các giá trị bên trái đều nhỏ hơn 23.
Bao gồm cả 15 đã biết không khớp.
23 lớn hơn 15 nên chỉ còn nửa phải.
Chỉ số 3 đã được kiểm và không bằng 23.
Lời giải
15 ở mid=3 nhỏ hơn 23. Vì dãy tăng, mọi chỉ số 0–3 đều có giá trị ≤15, nên left chuyển thành 4 và còn 4–6.
Bài luyện
Điều kiện nào bắt buộc để dùng đúng hàm `tim_nhi_phan_tang` trong bài?
Thứ tự tăng cho phép bỏ nửa chắc chắn không chứa k.
Hàm dùng được với kích thước khác.
Số âm vẫn so sánh tăng được.
Không cần biết k nằm ở đâu trước khi tìm.
Lời giải
Hàm quyết định bỏ trái hay phải dựa trên trật tự tăng. Nếu dãy không tăng, quyết định ấy có thể loại nhầm giá trị cần tìm.
Bài luyện
Khi `left > right` trong hàm tìm nhị phân, kết luận nào đúng?
left lúc này không còn là vị trí trong phạm vi hợp lệ.
Không còn chỉ số nào để kiểm.
Vòng while kết thúc.
Đổi chỗ sẽ phá điều kiện dừng.
Lời giải
Vòng lặp chỉ chạy khi left≤right. Khi left>right mà chưa return một chỉ số, không có phần tử phù hợp trong dãy đã xét đúng điều kiện.
Đang học