Binary Search
Halve the search range each step using an invariant, so a lookup in a million sorted items takes about twenty comparisons.
The problem
You have a sorted array of 10^6 numbers and 10^6 questions of the form: where does x first appear, and how many times does it appear?
1 of 9