Binary search

Look at the middle, discard the half that can't contain it. O(log n) on sorted data.

Each probe halves the candidates

• 1000 elements → ~10 probes
• 1,000,000 → ~20
• 1,000,000,000 → ~30
• lower_bound / upper_bound: where a value would go (more useful)

Watch the window collapse

21 elements, target 30 → found in 5 probes. Blue window halves every step.

O(log n) vs O(n)

Linear scan climbs and drops off the chart. Binary/bisect stay flat.

Famous for being buggy

• Off-by-one boundaries · (lo+hi)/2 overflow (lived in the JDK for years)
• Use a half-open window [lo, hi) consistently
• Silently requires sorted input
• Or just call bisect

Takeaway

Search sorted data with a logarithm, never a scan. Generalizes to "binary search on the answer". Next: quickselect.