Hai đầu đều thuộc vùng kết quả
A đã sắp xếp không giảm nên các phần tử bằng K, nếu có, nằm liền nhau. Cần trả (start,end), trong đó **cả start và end đều được tính**. Không có K thì trả (−1,−1).
Ví dụ A=[−1,2,2,5,5,5,9],K=5 cho (3,5), gồm các chỉ số 3,4,5. Kết quả là vùng chỉ số, không phải giá trị 5 hay độ dài vùng 3.
Tìm một vị trí rồi quét hai phía
```python
def findRange(A, left, right, K):
if left > right:
return -1, -1
mid = (left + right) // 2
if A[mid] == K:
start, end = mid, mid
while start >= left and A[start] == K:
start -= 1
while end <= right and A[end] == K:
end += 1
return start + 1, end - 1
if A[mid] < K:
return findRange(A, mid + 1, right, K)
return findRange(A, left, mid - 1, K)
```
Gọi với left=0,right=len(A)−1. Hai vòng while đi quá vị trí còn bằng K một bước, nên trả start+1,end−1. Kiểm biên đặt trước phép đọc A để không truy cập ngoài miền. Dãy rỗng cũng trả (−1,−1).
Khi đã tìm một vị trí, bước mở rộng quét qua các phần tử bằng K. Nếu cả dãy đều bằng K, bước này có thể xét cả dãy. Vì vậy bản đang dùng không có bậc O(log n) trong mọi trường hợp; cần tính cả công việc mở rộng vùng.
Kiểm vùng đầu, cuối và không có
Chạy bằng Python3:
```text
python3 g11-cs-thiet-ke-chia-de-tri.py vung "-1 2 2 5 5 5 9" 5
```
Cần nhận (3,5). Thử K=2 để nhận (1,2), K=9 để nhận (6,6), K=4 để nhận (−1,−1). Dãy `5 5 5` với K=5 phải cho (0,2); dãy rỗng cho (−1,−1).
Có thể kiểm vùng bằng lát cắt A[start:end+1] khi start≥0; mọi phần tử trong vùng phải bằng K, còn phần tử sát bên ngoài nếu có phải khác K. Không đọc lát cắt bằng hai chỉ số −1 của tín hiệu không tìm thấy.
Bài luyện
A=[−1,2,2,5,5,5,9],K=5. Cặp chỉ số cần trả là gì?
Bỏ mất phần tử chỉ số 3 và lấy thêm chỉ số 6.
Chưa bao phủ hai phần tử bằng 5 ở trước.
Ba phần tử bằng 5 ở chỉ số 3,4,5.
Chỉ số 6 chứa 9, ngoài vùng bằng K.
Lời giải
Đánh chỉ số từ 0: các giá trị 5 nằm tại 3,4,5. Vì end cũng thuộc vùng, kết quả là (3,5).
Bài luyện
Đã có start=3,end=5 hợp lệ. Lát cắt Python nào lấy đủ các phần tử trong vùng?
Lát cắt này chưa lấy phần tử chỉ số 5.
Lát cắt này bỏ phần tử chỉ số 3.
Hai cận bằng nhau tạo lát cắt rỗng.
Cận phải của lát cắt phải lớn hơn end một đơn vị.
Lời giải
Vùng gồm cả chỉ số 5, nhưng cận phải của lát cắt Python không được lấy. Do đó cần A[start:end+1]=A[3:6].
Bài luyện
Với cả dãy đều bằng K, vì sao bản findRange này có thể cần công việc tăng tuyến tính theo độ dài dãy?
Chi phí quét vùng phải được tính cùng phần tìm một vị trí.
Chia đôi không có quy tắc tổng quát như vậy.
Đoạn mã không tạo dãy mới.
Các vòng while có thể đọc nhiều phần tử bằng K.
Lời giải
Sau khi tìm được một vị trí, hai vòng while mở rộng sang hai phía cho tới biên vùng trùng. Nếu mọi phần tử đều bằng K, vùng ấy gồm cả dãy, nên công việc mở rộng có bậc O(n).
Đang học