Tìm một giá trị trong dãy
Ta cần biết có giá trị cần tìm không và, nếu có, nằm ở chỉ số nào. Dãy đã sắp xếp cho phép loại bỏ nhiều vị trí một lúc; dãy chưa sắp xếp thì không thể loại nửa dãy theo cùng cách.
Hai cách tìm
Tìm tuần tự so lần lượt các phần tử; dùng được khi chưa sắp xếp. Tìm nhị phân yêu cầu dãy có thứ tự phù hợp: so với phần tử giữa rồi giữ nửa có thể chứa giá trị. Trong bài, dãy tăng không giảm và cần tìm một vị trí bất kì khớp x, trả −1 nếu không có. Nếu có giá trị lặp, kết quả không mặc nhiên là vị trí đầu tiên.
Tìm nhị phân bằng mã
```python
def tim(a, x):
left, right = 0, len(a) - 1
while left <= right:
mid = (left + right) // 2
if a[mid] == x:
return mid
if a[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
```
Với [2,5,8,11,14] và x=11: giữa đầu là chỉ số 2, giá trị 8 nên giữ phần phải [3,4]. Giữa tiếp theo chỉ số 3 có 11; trả 3.
Thử vận dụng
Điều kiện nào cần cho tìm nhị phân kiểu trong bài?
Đúng: thứ tự cho phép loại vùng không thể chứa x.
Không cần các giá trị bằng nhau.
Độ dài chẵn/lẻ đều xử lí được.
Thuật toán dùng được cho dãy nhỏ và cả dãy rỗng.
Lời giải
Việc loại nửa dãy dựa vào thứ tự đã sắp; không cần độ dài chẵn hay lớn.
Tìm tuần tự
Trong [9,3,7,3], tìm tuần tự từ đầu và dừng ngay khi gặp 3: so 9 rồi 3, trả chỉ số 1. Nếu cần mọi vị trí, không dừng ở lần đầu mà tiếp tục tới hết, được 1 và 3. Yêu cầu kết quả quyết định điều kiện dừng.
Ví dụ xem cách làm
Dùng hàm tìm nhị phân trên với [2,5,8,11,14] và x=6. Các giá trị giữa được so là gì?
Lời giải
8, 2, 5. Sau so 8, right=1; so 2 tại mid=0 thì left=1; so 5 tại mid=1 thì left=2 > right=1, dừng và trả −1.
Ví dụ xem cách làm
Vì sao cập nhật left = mid thay vì mid + 1 có thể không dừng?
Lời giải
Khi mid = left và a[mid] < x, gán left = mid không thu hẹp đoạn. Lần sau có thể lặp lại cùng trạng thái. Cần loại vị trí giữa đã biết không khớp bằng mid + 1.
Những điều cần nhớ
Nêu rõ thứ tự dãy và loại vị trí cần tìm. Theo dõi cặp biên để bảo đảm mỗi bước thu hẹp đúng vùng có thể chứa đáp án.
Đang học