How to find if an array has at least 10 unique integers in $O(\log n)$?

Question

I am given a sorted array of integers. I want to find out if the array has at least 10 unique integers. I know this can easily be done with an algorithm that runs in $O(n)$ simply by going through each element and making comparisons, but how can this be done in $O(\log n)$ ?

Answer 1

It's sorted, so we have the smallest element to be the first element of the array. Given an element $k$, can you find the last occurrence of $k$ in the array (hint: see the comments)? Since it's the last occurrence of $k$ in the array, we know that the next element after that is different than $k$. If you can do that, then just repeat this 10 times.