Data Searching from a large data set without reading each element
Say you have $n$ entries, $m$ distinct letters, and the $i$-th letter occurs $k_i$ times. You can find the last occurrence of the $i$-th letter using a variant of binary search: Double your step size until you find a different letter (or run out of the array), do binary search between your last and second-to-last step. This takes about $2\log k_i$ many steps. So in total you need about

$$\sum_{i=1}^m \log k_i = \log \prod_{i=1}^{m} k_i$$

many steps. That product is biggest when all terms are equal, so you have something like $m\log (n/m)$ many steps.

Naively implemented, this is not always better than looking at all elements though. If you work out all the details, you'll see that for example when $m=n$ you have to be a bit careful.