Tìm mốt trên dãy đã sắp xếp

Mốt (mode) là giá trị có số lần xuất hiện nhiều nhất. Dãy A đã không giảm nên các giá trị bằng nhau nằm liền nhau. Với A=[−1,2,2,2,5,5], mốt là 2 với 3 lần xuất hiện. Chọn mid; quét trái/phải từ mid để đếm trọn vùng bằng A[mid] trong miền đang xét. Tìm thêm kết quả của nửa trái và nửa phải rồi so ba tần số. Một vùng giá trị hoặc đi qua mid, hoặc nằm hoàn toàn ở một phía, nên các khả năng này phủ đủ ứng viên.

```python def mode(A, left, right): if left > right: return None, 0 mid = (left + right) // 2 i = j = mid while i > left and A[i] == A[i - 1]: i -= 1 while j < right and A[j] == A[j + 1]: j += 1 m0, k0 = A[mid], j - i + 1 m1, k1 = mode(A, left, mid - 1) m2, k2 = mode(A, mid + 1, right) if k0 >= k1 and k0 >= k2: return m0, k0 if k1 >= k0 and k1 >= k2: return m1, k1 return m2, k2 ``` Gọi mode(A,0,len(A)−1). Dãy rỗng trả (None,0). Nếu có nhiều mốt, bài toán chỉ cần một; mã ưu tiên vùng qua mid khi đồng hạng, sau đó nửa trái, rồi nửa phải. Không khẳng định lúc nào cũng trả mốt nhỏ nhất. Hàm có quét vùng và tìm cả hai phía, nên không suy ra O(log n) chỉ từ việc chia đôi. Không tự sắp xếp trong hàm; cần đúng điều kiện không giảm trước khi gọi.