Chưa sắp xếp thì không loại nửa theo giá trị giữa
Với dãy chưa sắp xếp, so sánh A[mid] với K không cho biết các phần tử bằng K nằm ở phía nào. Cần xét phần tử giữa và giải cả hai miền còn lại.
Ví dụ A=[4,1,4,0,4],K=4 có ba lần xuất hiện ở chỉ số 0,2,4. Phần tử giữa bằng 4 vẫn chưa đủ để biết số lần xuất hiện ở hai phía.
Ba phần không chồng lên nhau
```python
def count_any(A, left, right, K):
if left > right:
return 0
mid = (left + right) // 2
count = 1 if A[mid] == K else 0
return (count + count_any(A, left, mid - 1, K)
+ count_any(A, mid + 1, right, K))
```
Phần tử mid được xét một lần; miền trái kết thúc tại mid−1 và miền phải bắt đầu tại mid+1, nên không đếm lặp mid. Gọi với left=0,right=len(A)−1. Cơ sở miền rỗng trả 0, sau đó cộng số đếm khi các lời gọi trả về.
Với dãy mẫu, phần giữa góp 1, hai nửa góp 1 và 1; tổng là 3. Hàm chỉ đọc và không sửa thứ tự của A.
Đối chiếu với bản quét
Chạy:
```text
python3 g11-cs-thuc-hanh-tim-kiem.py bat-ky "4 1 4 0 4" 4
```
Hai bản cần cho 3. Thử thêm dãy rỗng, toàn bằng K, không có K và K ở cả hai đầu. Không cần sắp xếp dãy cho bản này.
Tuy mỗi lần chia miền tạo các bài toán nhỏ hơn và độ sâu giảm theo log n, tổng cộng vẫn phải xét mọi phần tử. Theo mô hình phép tính cơ bản, bản đếm này có bậc O(n), tương đương bản quét; dùng đệ quy không tự biến tổng công việc thành O(log n).
Bài luyện
Với A=[4,1,4,0,4],K=4, count_any trên cả dãy trả bao nhiêu?
Ba phần tử bằng 4 ở chỉ số 0,2,4.
1 chỉ tính phần tử giữa.
Còn thiếu một trong hai phía hoặc phần tử giữa.
5 là số phần tử, không phải số phần tử bằng 4.
Lời giải
Phần tử giữa A[2]=4 góp 1. Nửa trái [4,1] góp 1 và nửa phải [0,4] góp 1, nên tổng bằng 3.
Bài luyện
Vì sao phải đếm cả hai nửa khi dãy chưa sắp xếp?
Hai miền nhỏ đã loại mid để không đếm lặp.
K có thể xuất hiện ở bất kì phía nào.
Chỉ những phần tử bằng K mới góp vào số đếm.
Thuật toán này không cần sửa dãy.
Lời giải
Không có tính chất thứ tự để suy ra một phía không chứa K. Do đó cần xét cả hai nửa, rồi cộng với đóng góp của phần tử giữa.
Bài luyện
Vì sao bản count_any có bậc O(n) dù chia đôi miền?
Hai miền đều bỏ phần tử giữa nên nhỏ hơn.
Hàm đã có nhánh left>right trả 0.
Độ sâu nhỏ không có nghĩa tổng số phần tử được xét cũng nhỏ.
Bậc phụ thuộc bài toán và số nhánh cần giải.
Lời giải
Mỗi phần tử được chọn làm phần tử giữa đúng một lần trên cây chia miền. Có n phần tử cần xét, nên tổng công việc tăng tuyến tính, dù độ sâu cây chỉ tăng theo log n.
Đang học