Watch it run
Step through the search: each comparison throws away half the remaining space. Change the array and target, or scrub backwards if a step went by too fast.
1/7Search space is the whole array. Looking for 38.
A template you won't get wrong
Use a half-open [lo, hi) and converge on the first index that satisfies a
predicate. This one template handles "find x", "lower bound", "first true".
def lower_bound(a, target):
lo, hi = 0, len(a) # half-open [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target: # predicate: "too small"
lo = mid + 1
else:
hi = mid # mid might be the answer → keep it in range
return lo # first index with a[i] >= target
The invariant: everything < lo fails the predicate, everything >= hi
satisfies it. The loop shrinks the unknown region until lo == hi.
The real SDE2 skill: binary search on the answer
When the answer is a number and "does value x work?" is monotonic (if x
works, so does every larger/smaller x), binary-search the answer, not an
array.
# Min ship capacity to deliver all packages in <= D days.
def min_capacity(weights, D):
def feasible(cap):
days, cur = 1, 0
for w in weights:
if cur + w > cap: days, cur = days + 1, 0
cur += w
return days <= D
lo, hi = max(weights), sum(weights) # capacity search space
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid): hi = mid # works → try smaller
else: lo = mid + 1 # doesn't → go bigger
return lo
"Minimum/maximum X such that a condition holds", "smallest capacity / largest minimum / fastest speed" + a monotonic feasibility check ⇒ binary search on the answer. Complexity is O(n log(range)) — the log of the value range, not the array length.
1. An array has 1,000,000 sorted elements. Roughly how many comparisons does binary search need in the worst case?
2. In the half-open template ([lo, hi), while lo < hi), why is `hi = mid` safe but `lo = mid` an infinite-loop bug?
3. “Minimum ship capacity to deliver all packages within D days” is solved with binary search because…
Practice — climb the ladder
Binary search needs ONE thing: a monotonic yes/no boundary. The ladder moves from searching arrays to searching ANSWER SPACES — the big leap.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
bounds discipline — no off-by-ones, ever- Binary SearchEasy
The template itself — lo/hi/mid until your invariant survives any input.
Lower bound — WHERE the boundary lands when the target is absent.
Core
broken invariants and first/last boundariesTwo boundary searches (leftmost + rightmost) — bias the mid correctly.
One half is always sorted — decide which, then discard the other.
Searching for a PROPERTY (the pivot), not a value.
- Koko Eating BananasMedium
Binary search ON THE ANSWER — guess a speed, check feasibility, halve.
Same answer-space pattern — min capacity whose check passes.
Stretch
the two famous finalsAnswer-space search where the check is itself greedy — two patterns stacked.
Partition search across two arrays — the hardest classic binary search.