Find a range that must contain the target by checking positions 1, 2, 4, 8, … until one holds a value at least as big as the target, then binary search that range. The cost depends on where the target is, not on how long the array is.
- Average time
- O(log n)
- Space
- O(1)