Sắp xếp theo trường được tìm
Dữ liệu giả định gồm:
| Tên mẫu | Điểm |
|---|---|
| Mẫu A | 6.5 |
| Mẫu B | 7.25 |
| Mẫu C | 8.0 |
| Mẫu D | 9.5 |
Cần tìm theo điểm nên các bản ghi phải theo thứ tự không giảm của **điểm**, không chỉ theo tên. Tách hai danh sách names và scores theo cùng thứ tự để names[i] luôn thuộc đúng scores[i]. Nếu sắp xếp lại bản ghi thì phải giữ cả tên và điểm đi cùng nhau.
Kiểm chỉ số trước khi đọc tên
Hàm binarySearch là hàm đã dùng ở bài trước; có sẵn trong tệp thực hành:
```python
def find_record(DS, K):
names = [row[0] for row in DS]
scores = [row[1] for row in DS]
index = binarySearch(scores, 0, len(scores) - 1, K)
if index < 0:
return None
return names[index]
```
Tìm 7.25 cho chỉ số 1 và tên Mẫu B. Tìm 7.0 không có thì trả None để phần chương trình chính thông báo “không có”. Phải kiểm index trước khi đọc names[index]: trong Python, names[−1] của danh sách không rỗng lại là tên cuối, không phải thông báo không tìm thấy.
Nếu các điểm trùng nhau, thuật toán có thể trả một tên có điểm đúng; yêu cầu này chưa bắt liệt kê mọi tên hoặc chọn tên đầu tiên.
Nhập và kiểm dữ liệu tìm kiếm
Tải mã, mở terminal tại thư mục chứa tệp rồi chạy bằng Python3:
```text
python3 g11-cs-chia-de-tri.py tim
python3 g11-cs-chia-de-tri.py diem
```
Ở chế độ tim, nhập `100 200 300` rồi nhập `100`; cần nhận chỉ số 0. Nhập `250` phải nhận −1. Thử dòng dãy rỗng rồi nhập một số: nhận −1; nhập dãy `3 1 2` phải báo chưa đúng thứ tự, không chạy tìm nhị phân trên dữ liệu ấy.
Ở chế độ diem, nhập 7.25 cần nhận Mẫu B; nhập 7.0 phải báo “không có”. Tên và điểm đều giả định. Mẫu chỉ nhận điểm hữu hạn trong khoảng 0–10; nhập chữ hoặc giá trị ngoài mẫu phải báo lỗi. Nếu máy dùng lệnh python để gọi Python3 thì dùng tên lệnh tương ứng.
Bài luyện
Với bảng giả định trong bài, tìm điểm 7.25 cần nhận tên nào?
Mẫu B và điểm 7.25 cùng ở chỉ số 1.
Mẫu A có điểm 6.5.
Mẫu C có điểm 8.0.
Mẫu D có điểm 9.5.
Lời giải
Danh sách điểm là [6.5,7.25,8.0,9.5]. Giá trị 7.25 ở chỉ số 1; danh sách tên cùng thứ tự có names[1]=Mẫu B.
Bài luyện
Điều kiện nào cần được giữ để tìm nhị phân theo điểm đúng?
Thứ tự không giảm cho phép các giá trị bằng nhau.
Thứ tự điểm giúp loại nửa miền và liên hệ cùng hàng giúp trả đúng tên.
Thứ tự tên không tạo thứ tự cho trường điểm.
Cách đó có thể làm tên thuộc sai điểm.
Lời giải
Phép so sánh giữa cần dựa trên dãy điểm đã sắp xếp. Đồng thời names[i] phải thuộc scores[i], nên không được làm mất liên hệ tên–điểm khi tách hoặc sắp xếp dữ liệu.
Bài luyện
Không có điểm cần tìm và binarySearch trả −1. Vì sao phải kiểm trước names[index]?
Vị trí đầu thường có chỉ số 0.
Không có căn cứ để gán điểm cần tìm cho tên cuối.
−1 là tín hiệu không thấy của hàm, nhưng cũng là chỉ số âm hợp lệ với danh sách không rỗng.
Python không tự hiểu quy ước đầu ra của hàm tìm kiếm.
Lời giải
Hàm tìm kiếm quy ước −1 là không tìm thấy. Nếu đưa −1 vào phép đọc danh sách không rỗng, Python lấy phần tử cuối. Vì vậy phải kiểm index<0 và thông báo không có trước khi đọc tên.
Đang học