visual walkthrough
Binary Search
Nail one bug-free template before anything else.
The idea
Look at the middle number. If it is too small, everything to its left is smaller still, so that whole half can be thrown away. If it is too big, throw away the right half. The window halves every step.
Doubling the array adds only one extra step, which is why a million numbers need about 20 looks instead of a million.
Complexity
| approach | time | space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Binary search | O(log n) | O(1) |