What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?
I am trying binary search on the array A.
- x = A[mid], where mid is the middle element of the array.
- Compare x with A[n/4] and A[3n/4].
- If x = A[n/4] and x ≠ A[3n/4] then search in A to A[3n/4 + 1].
- If x ≠ A[n/4] and x = A[3n/4] then search in A[n/4 + 1] to A[n].
- If x ≠ A[n/4] and x ≠ A[3n/4] then it is a no instance.
- If x = A[n/4] and x = A[3n/4] then it is a yes instance.
Running Time: $T(n) = T(3n/4) + O(1)$ which is $O(\log n)$ in asymptotic sense. At each step I am doing two comparisons so $2\log_4n$ if $n = 4^k$. Is there any better (optimal) algorithm to solve the problem mentioned above?
Also, I don't know how to prove the lower bound.