When the answer space is sorted, halving it each step beats scanning everything.
Binary search is the first pattern that teaches you to stop linear scanning when the input has order.
When to use it
Array is sorted (or you can sort once)
You're searching for a value, boundary, or minimum that satisfies a condition
The predicate is monotonic: if works(x) is true, works(x+1) is also true (or vice versa)
Template (lower bound)
python
def lower_bound(nums: list[int], target: int) -> int: lo, hi = 0, len(nums) while lo < hi: mid = (lo + hi) // 2 if nums[mid] < target: lo = mid + 1 else: hi = mid return lo
Complexity
Approach
Time
Space
Linear scan
O(n)
O(1)
Binary search
O(log n)
O(1)
Interview tip
Say the invariant out loud: "Everything before lo is too small; everything from hi onward is valid." That one sentence separates a memorized template from someone who understands why it works.
Common mistakes
Off-by-one on left/right bounds (<= vs <)
Integer overflow in (lo + hi) // 2 — use lo + (hi - lo) // 2
Forgetting the array must stay sorted after mutations