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. After k halvings the remaining range is n / 2k; set that to 1, giving k = log₂ n — 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;

// 3. upper bound: first index with a[i] > t    (half-open invariant: a[0..lo) <= t, a[hi..n) > t)
int lo=0, hi=n;
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.

Floating-Point Binary Search (Search on Reals)

When searching for a double or float answer (e.g. finding a square root, or solving an optimization problem with fractional values), you cannot use integer division or simple pointer collapse. A common mistake is writing a condition like while (hi - lo > epsilon) where epsilon is a small threshold (e.g. 1e-9). If the values of lo and hi converge near the limits of double-precision floating-point numbers, this loop can run infinitely because hi - lo will never become smaller than epsilon due to rounding errors.

The Fix: Instead of checking the delta, run the loop a fixed number of times (usually 100). Each iteration halves the search space, and after 100 iterations, the search space is scaled down by a factor of 2-100 ≈ 10-30, which is far beyond the precision limits of standard 64-bit doubles (15-17 decimal digits). This guarantees convergence without risk of hanging.

// Float Binary Search Template
double lo = min_val, hi = max_val;
for (int iter = 0; iter < 100; iter++) {
    double mid = lo + (hi - lo) / 2.0;
    if (isValid(mid)) {
        lo = mid;      // or hi = mid, depending on monotonic direction
    } else {
        hi = mid;
    }
}
return lo;

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. Termination proof for the exact template: every iteration moves lo up or hi down by at least 1, so the range strictly shrinks. Fastest sanity check is a 2-element trace — a=[2,5], t=3: mid=0, 2<3 → lo=1; mid=1, 5>3 → hi=0; lo>hi → -1, no spin.
• 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 derive the template from the invariant (lo is the first index that could still hold the answer, hi is just past the end).
• 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.