Find a repeated element in linear time
If you choose $\frac{n}{2}$ as the pivot to do the partition, you just need then to continue the search in the half containing strictly more than $\frac{n}{2}$ elements.
That way you don't have to check both halves.