Instead of always probing the middle, estimate where the target should be from its value: if it is 80% of the way from the smallest to the largest value, look 80% of the way along. On evenly spread values the guesses close in very fast.
- Average time
- O(log log n)
- Space
- O(1)