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