We are given a sorted array$A[1..n]$, we are searching to find an element that repeated $\frac{n}{5}$ times in array.How we can do it in $logn$?
I find an solution in $O(n)$,with checking each element $i$,and calculate it appearance in interval $A[i+\frac{n}{5}]-A[i]+1$. If $A[i]=A[i+\frac{n}{5}]$ then we find it.
But how we can decrease it to $logn$?
Note that the interval you're looking for is so big that it must hit one of five evenly-spaced indexes between 0 and $n$ (say $n/6,2n/6,3n/6,4n/6,5n/6$), so we have five candidate values for the repeated element. Use two binary searches for each candidate value to find its start and end indexes.