Lower bound for finding repeated elements in sorted array

Question

This is inspired by [1] (which still needs answers).

What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how to determine whether there exists some element which occurs more than $\lfloor n/k \rfloor$ times?

---

Note 1: The original problem [1] focuses on $k=2$, i.e., the "majority detection" problem. There is a simple $\Theta(\log n)$ algorithm for it: Only the median, called $m$, can be the majority. We can learn the length of the $m$ contiguous block using binary search.

However, is $\Omega(\log n)$ a lower bound for $k = 2$?

Note 2: For unsorted array, [2] gives an optimal $O(n \log k)$ algorithm. The lower bound is proved using the decision-tree technique (section 5). I failed to extend it to the sorted case.

---

[1] Lower bound of finding majority element in an ordered array. @ cs.exchange

[2] Finding Repeated Elements by J. Misra and David Gries, TR, 1982.

Answer 1

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.