Binary Search — Templates, the Trace & Search-on-Answer

The idea: throw away half the data every step

On sorted data, you never need to look at most of it. Compare the middle: if it's too small, the answer is to the right; too big, to the left. Each comparison halves the search space — O(log n). The hard part isn't the idea, it's writing the boundaries without an off-by-one or infinite loop.

The trace (find 23)

step	lo	hi	mid	a[mid]	action
1	0	7	3	16	16 < 23 → lo = 4
2	4	7	5	42	42 > 23 → hi = 4
3	4	4	4	23	found ✓

The three templates (learn all three)

// 1. exact match
int lo=0, hi=n-1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;        // NOT (lo+hi)/2 — that overflows
    if (a[mid] == t) return mid;
    else if (a[mid] < t) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

// 2. lower bound: first index with a[i] >= t   (great for "insert position", ranges)
int lo=0, hi=n;                          // hi = n, half-open
while (lo < hi) { int mid=lo+(hi-lo)/2; if (a[mid] < t) lo=mid+1; else hi=mid; }
return lo;

The real interview skill: binary search on the answer

When the array isn't the thing you search — you search a monotonic predicate. "Minimum capacity to ship in D days", "smallest x with f(x) true": if can(x) is false-false-…-true-true, binary-search the boundary. Same code, can(mid) instead of a[mid]==t.

Pitfalls

• Overflow: (lo+hi)/2 overflows int; use lo + (hi-lo)/2.
• Infinite loop: if mid doesn't move a boundary (e.g. lo=mid with floor division), it spins. Match the < vs <= and the update to the template.
• Unsorted input — binary search is meaningless; sort first (or it's the wrong tool).

Takeaways

• Halve each step → O(log n); the trap is boundaries, so memorise the templates.
• Three forms: exact, lower-bound, upper-bound; lower-bound (half-open) is the most reusable.
• Binary search on the answer (monotonic predicate) is the high-value pattern.

---

Re-authored for this guide; pointer-collapse diagram hand-authored as SVG. See also: Searching, Sorting, and "binary search on answer" problems.

I just read a lesson on **Binary Search — Templates, the Trace & Search-on-Answer** (DSA) and want to truly understand it. Explain Binary Search — Templates, the Trace & Search-on-Answer from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Binary Search — Templates, the Trace & Search-on-Answer** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Binary Search — Templates, the Trace & Search-on-Answer** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Binary Search — Templates, the Trace & Search-on-Answer** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.