Tệp điểm mẫu
Tạo tệp `diem_tang.txt` trong cùng thư mục chạy mã. Mỗi dòng là một điểm giả đã sắp không giảm:
```text
5.5
6.0
7.0
7.0
8.5
```
Bài toán hỏi một điểm có xuất hiện không và, nếu có, ở một dòng nào. Hai số 7.0 cho thấy hàm nhị phân chỉ cần trả một vị trí khớp. Nếu dữ liệu chưa sắp, không dùng hàm này.
Đọc và tìm bằng nhị phân
```python
def tim_nhi_phan_tang(a, k):
trai, phai = 0, len(a) - 1
while trai <= phai:
giua = (trai + phai) // 2
if a[giua] == k:
return giua
if a[giua] < k:
trai = giua + 1
else:
phai = giua - 1
return -1
with open("diem_tang.txt", "r", encoding="utf-8") as f:
diem = [float(dong) for dong in f]
for can_tim in [7.0, 9.0]:
chi_so = tim_nhi_phan_tang(diem, can_tim)
if chi_so == -1:
print(can_tim, "không có trong tệp")
else:
print(can_tim, "ở dòng", chi_so + 1)
```
Kết quả là `7.0 ở dòng 3` rồi `9.0 không có trong tệp`. Giữa đầu tiên của năm phần tử là chỉ số 2, tức dòng thứ 3. Python đánh chỉ số từ 0, còn dòng đầu tiên thường được gọi là dòng 1 nên phải cộng 1. Một dòng trống hoặc chữ không phải số sẽ làm `float` báo lỗi; sửa tệp đầu vào. Hàm tin vào điều kiện tệp đã sắp không giảm, không tự kiểm thứ tự.
Đổi sang dãy giảm và tra khoảng
Nếu tệp sắp không tăng, dùng hàm `tim_nhi_phan_giam` ở L13: phần tử giữa lớn hơn điểm cần tìm thì đi sang phải. Với yêu cầu tìm **mọi** tên có điểm từ 6 đến 8, dùng tệp cặp tên–điểm ở L15 và duyệt mọi dòng với điều kiện `6 <= diem <= 8`; cả hai đầu mút đều được lấy. Nếu dữ liệu đã sắp theo điểm, có thể tìm biên đầu có điểm ≥6 và biên đầu có điểm >8 bằng cách thu hẹp nửa dãy, rồi lấy các bản ghi giữa hai biên. Khi sắp, phải giữ tên đi cùng điểm; sắp riêng điểm sẽ làm sai kết quả tên.
Bài luyện
Chỉ số Python 2 ứng với dòng thứ mấy của tệp mẫu?
Dòng 1 có chỉ số 0.
Dòng 2 có chỉ số 1.
Số dòng bằng chỉ số cộng 1.
Dòng 4 có chỉ số 3.
Lời giải
Danh sách đọc từ tệp bắt đầu ở chỉ số 0. Chỉ số 2 ứng với dòng thứ 3.
Bài luyện
Vì sao có thể bỏ nửa trái khi dãy tăng và phần tử giữa nhỏ hơn điểm cần tìm?
Thứ tự tăng chứng minh nửa trái không thể chứa điểm lớn hơn phần tử giữa.
Nửa trái có thể có phần tử.
Điểm cần tìm có thể ở vị trí khác.
float chỉ chuyển kiểu số.
Lời giải
Trong dãy tăng, mọi giá trị bên trái và tại giữa đều không lớn hơn giá trị giữa. Nếu giá trị giữa < k thì bỏ được phần ấy.
Bài luyện
Nếu tệp có hai dòng điểm 7.0, hàm nhị phân mẫu bảo đảm điều gì?
Hàm dừng ngay ở một lần khớp.
Hàm trả một số nguyên.
Vị trí gặp trước tùy các bước lấy giữa.
Dãy có giá trị trùng vẫn sắp được.
Lời giải
Khi a[giua]==k, hàm trả giua ngay; nó không tìm thêm các giá trị bằng k ở bên cạnh.
Đang học