Write bug-free binary search. Explain lower_bound vs upper_bound.
Everyone "knows" binary search; few write it without off-by-one. Interviewers test this because the bug rate is high.
Classic: find exact target. while (l <= r): mid = (l+r)/2; if arr[mid]==t return; if less l=mid+1 else r=mid-1.
lower_bound: first index where arr[i] >= target. while (l < r): mid = (l+r)/2; if arr[mid] < target: l=mid+1; else r=mid. Returns l.
upper_bound: first index where arr[i] > target. Same as lower_bound with <= instead of <.
Binary search on answer: when the answer is monotone in some predicate (can we finish all tasks with K workers?). Binary search over K.
Rotated sorted array: compare mid to l (or r) to decide which half is sorted, then check if target is in that half.
I keep two templates memorized. For 'find exact target': `while (l <= r) { m = l + (r-l)/2; if (eq) return m; if (less) l = m+1; else r = m-1; }` — inclusive bounds, l>r means miss. For 'first position satisfying predicate': `while (l < r) { m = (l+r)/2; if (pred(m)) r = m; else l = m+1; }` — l==r is the answer. lower_bound is this template with pred = arr[m] >= target; upper_bound with pred = arr[m] > target. 'Binary search on answer' is the same template where pred is a feasibility check — capacity-to-ship-in-D-days, smallest-max, etc. For rotated arrays I branch: whichever half (l..m or m..r) is sorted, check if target fits in its range.
Use `mid = l + (r-l)/2` not `(l+r)/2` to avoid int overflow on large indices.
Decide inclusive or exclusive bounds FIRST and stay consistent — mixing is the #1 bug source.
HireMe AI (即答侠) provides the two templates with assertions — paste and adapt.
Different invariants. Basic search shrinks both sides when mid fails; lower_bound keeps r as "candidate answer" so never eliminates it.
Only if there's a monotone property over the search domain. "Search on answer" is the typical way unsorted problems become binary-searchable.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free