Giá trị bằng chính chỉ số của nó
Phần tử cố định là phần tử ở chỉ số i thỏa A[i]=i. Chỉ số được tính từ 0. Với A=[−2,0,2,5,9]:
| i | A[i] | A[i]=i? |
|---|---|---|
| 0 | −2 | Không |
| 1 | 0 | Không |
| 2 | 2 | Có |
| 3 | 5 | Không |
| 4 | 9 | Không |
Hàm cần trả một chỉ số phù hợp, ở đây là 2; nếu không có thì trả −1. Khi có nhiều phần tử cố định, yêu cầu này chưa bắt trả chỉ số nhỏ nhất.
Điều kiện là số nguyên và tăng thực sự
Bản tìm một nhánh dưới đây cần **dãy số nguyên tăng thực sự**: $A[0]<A[1]<\cdots<A[n-1]$. Hai số nguyên liên tiếp theo thứ tự ấy tăng ít nhất 1.
Nếu A[mid]<mid thì $A[mid-1]\le A[mid]-1<mid-1$; tiếp tục về trái đều có A[i]<i, nên chỉ cần tìm bên phải. Nếu A[mid]>mid, lập luận tương tự cho thấy bên phải có A[i]>i, chỉ cần tìm bên trái. Nếu A[mid]==mid thì đã tìm thấy.
Điều kiện tăng thực sự không cho phép các giá trị trùng; bài sau xử lí trường hợp ấy.
So sánh giá trị giữa với chỉ số giữa
```python
def fixvalue(A, left, right):
if left > right:
return -1
mid = (left + right) // 2
if A[mid] == mid:
return mid
if A[mid] < mid:
return fixvalue(A, mid + 1, right)
return fixvalue(A, left, mid - 1)
```
Gọi với left=0,right=len(A)−1. Ví dụ trên có mid=2 và A[2]=2 nên trả 2 ngay. Khi không trùng, mỗi lần chỉ còn một nửa miền; theo mô hình phép tính cơ bản, bậc thời gian là O(log n). Dãy rỗng trả −1.
Trong tệp thực hành, chạy co-dinh với --kieu tang để dùng bản này; tệp kiểm dữ liệu là số nguyên tăng thực sự trước khi gọi.
Bài luyện
Theo bảng A=[−2,0,2,5,9], chỉ số nào là chỉ số của phần tử cố định?
A[0]=−2, khác chỉ số 0.
A[1]=0, khác chỉ số 1.
Dãy chỉ có các chỉ số 0–4; 5 là một giá trị ở chỉ số 3.
A[2]=2.
Lời giải
Phần tử cố định phải có giá trị bằng chỉ số. Trong bảng chỉ có A[2]=2, nên chỉ số cần trả là 2.
Bài luyện
Bản fixvalue chỉ tìm tiếp một nửa trong bài cần điều kiện nào?
Mỗi bước tăng ít nhất 1 giúp suy ra phía không thể có điểm cố định.
Chưa có căn cứ loại một nửa khi dữ liệu tùy ý.
Giá trị trùng làm lập luận tăng ít nhất 1 không còn đúng.
Tính chẵn/lẻ của độ dài không tạo tính chất cần thiết.
Lời giải
Lập luận loại nhánh dùng A[i+1]≥A[i]+1, được bảo đảm khi dữ liệu là số nguyên và tăng thực sự. Chỉ không giảm hoặc độ dài chẵn chưa đủ.
Bài luyện
Khi A[mid]<mid trên dãy đáp ứng điều kiện, vì sao tìm tiếp bên phải?
Tìm thấy cần dấu bằng A[mid]==mid.
Khoảng cách tăng của số nguyên loại được phía trái.
Có thể không có phần tử cố định ở cả dãy.
Thuật toán tìm không sửa dữ liệu như vậy.
Lời giải
Do dãy nguyên tăng thực sự, càng đi về trái giá trị giảm ít nhất một đơn vị mỗi bước. Từ A[mid]<mid suy ra A[i]<i ở phía trái; chỉ phía phải còn có thể chứa kết quả.
Đang học