Giá trị trùng có thể làm mất kết quả nếu loại sai nửa
Với A=[0,0,0], phần tử cố định là A[0]=0. Lần đầu mid=1 và A[1]=0<1. Nếu áp dụng bản chỉ dành cho tăng thực sự để bỏ bên trái, sẽ bỏ mất kết quả ở chỉ số 0.
Vì vậy cần một cách tìm có thể xét cả hai phía. Không sắp xếp lại dữ liệu để tìm phần tử cố định của dãy gốc: chẳng hạn [1,0] không có phần tử cố định, còn sau sắp xếp thành [0,1] thì cả hai vị trí đều cố định. Đó đã là một dãy khác.
Bản tổng quát giữ nguyên chỉ số
```python
def findFix(A, left, right):
if left > right:
return -1
mid = (left + right) // 2
if A[mid] == mid:
return mid
index = findFix(A, mid + 1, right)
if index >= 0:
return index
return findFix(A, left, mid - 1)
```
Bản này dùng cho dãy số nguyên bất kì, kể cả chưa sắp xếp. Nếu chưa thấy ở giữa, tìm bên phải rồi tìm bên trái khi cần. Hàm trả một chỉ số phù hợp hoặc −1, không hứa trả chỉ số đầu tiên. Trường hợp xấu nhất có thể xét mọi phần tử, bậc O(n).
Dãy không giảm cho phép kiểm thêm hai biên
Với dãy nguyên không giảm, có thể dùng hàm dưới cùng findFix vừa nêu:
```python
def findFixPoint(A, left, right):
if left > right:
return -1
mid = (left + right) // 2
if A[mid] == mid:
return mid
if mid + 1 <= A[right]:
index = findFix(A, mid + 1, right)
if index >= 0:
return index
if mid - 1 >= A[left]:
index = findFix(A, left, mid - 1)
if index >= 0:
return index
return -1
```
Nếu A[right]<mid+1, mọi giá trị bên phải đều nhỏ hơn chỉ số tương ứng, nên bỏ phía ấy. Nếu A[left]>mid−1, phía trái không có phần tử cố định. Những phía chưa loại được vẫn dùng bản tổng quát để tìm; trường hợp xấu nhất vẫn O(n).
Với A=[0,0,0], kiểm biên bỏ phía phải và tìm bên trái, nhận chỉ số 0. Trong tệp mẫu, chọn --kieu khong-giam cho bản này, --kieu bat-ky cho findFix; không dùng --kieu tang khi có giá trị trùng.
Bài luyện
A=[0,0,0] có phần tử cố định ở đâu?
A[2]=0, khác 2.
Giá trị trùng không loại bỏ định nghĩa A[i]=i.
A[0]=0.
A[1]=0, khác 1.
Lời giải
Kiểm từng vị trí: A[0]=0 đúng, A[1]=0≠1 và A[2]=0≠2. Vì vậy có đúng phần tử cố định ở chỉ số 0.
Bài luyện
Có nên sắp xếp [1,0] rồi dùng kết quả để kết luận phần tử cố định của dãy gốc không?
Vị trí các phần tử có thể thay đổi.
Trong [1,0], cả hai giá trị đều khác chỉ số của chúng.
Yêu cầu vẫn là tìm một chỉ số phù hợp.
Dãy gốc và dãy sau sắp xếp là hai bài toán khác nhau về chỉ số.
Lời giải
Dãy [1,0] có A[0]=1≠0 và A[1]=0≠1 nên không có phần tử cố định. Sau sắp xếp [0,1] lại có cả hai; không được dùng kết quả của dãy mới cho dãy gốc.
Bài luyện
Vì sao không kết luận hai bản tìm tổng quát trong bài luôn có bậc O(log n)?
Không có bảo đảm mỗi lần chỉ cần giải một nhánh.
Bậc thời gian không suy ra chỉ từ việc có if.
Các miền nhỏ vẫn được tạo, nhưng có thể cần giải cả hai.
Đó không phải hành vi ở trường hợp xấu nhất.
Lời giải
Khi không loại được đủ các nhánh hoặc chưa tìm thấy, bản tổng quát tiếp tục tìm nhiều phần của dãy. Tổng số phần tử có thể được xét là n, nên trường hợp xấu nhất có bậc O(n).
Đang học