Binary Search Interview Boundary Bugs

Published 2026-09-30 · Luna Interview

Binary search interview failures are rarely about the idea “look at the middle.” They are about boundaries: off-by-one left/right updates, unclear return values, and predicates that are not actually monotonic. This guide catalogs the common boundary bugs and gives talk tracks that keep the loop correct under pressure.

The contract you must state

Binary search needs a monotonic predicate on a search space: once the answer flips from false to true (or values go from too small to too big), it never flips back.

Talk track:

“I’ll binary search on X because if a capacity of m works, every larger capacity also works.”

If you cannot say that sentence, do not binary-search yet.

Template A — classic index search

left ← 0
right ← n - 1
while left <= right:
  mid ← left + (right - left) // 2
  if a[mid] == target: return mid
  if a[mid] < target: left ← mid + 1
  else: right ← mid - 1
return -1

Boundary notes:

left <= right pairs with mid±1 updates
Empty array: loop never runs, return -1
Single element: mid is that element

Template B — lower bound (first true)

left ← 0
right ← n  # half-open [left, right)
while left < right:
  mid ← left + (right - left) // 2
  if predicate(mid):
    right ← mid
  else:
    left ← mid + 1
return left

Use when searching for the first index where a condition holds. Returning left after the loop is the usual answer.

Mid calculation bugs

Prefer left + (right - left) // 2 to avoid overflow in fixed-width integers (say it even in Python—shows habit)
Do not use floats for indices
On even lengths, know which side your mid biases toward and stay consistent

Left/right update bugs (the infinite loop zone)

Mistake	Symptom
`right ← mid` when you needed `mid - 1` with `left <= right`	Infinite loop or wrong branch
`left ← mid` without guaranteeing progress	Infinite loop when left stays put
Mixing closed and half-open conventions	Off-by-one returns
Updating both pointers wrong on equality	Skips the real answer

Progress rule: every iteration must shrink the search space. If mid can equal left and you set left ← mid, you may stall—use left ← mid + 1 or a different template.

Answer-on-value vs answer-on-index

Bugs appear when the prompt asks for a value (minimum capacity) but you binary-search indices of an array without defining the predicate on the value domain.

Answer-space search talk track:

“Low = max(single pile), high = sum(piles); mid is a candidate capacity; predicate is ‘can finish in H hours.’”

Keep low/high as inclusive values and document what you return when predicate becomes true.

Rotated array and duplicates

Rotated sorted array: identify which half is sorted before discarding
Duplicates: a[mid] == a[right] may force right -= 1—mention O(n) worst case honestly
Do not assume strict increase without asking

First five minutes

Confirm sorted / monotonic predicate
Choose index search vs answer-space search
Pick closed vs half-open template and stick to it
Define what equality means (found / go left for lower bound)
Dry-run two cases: target missing, target at ends

Dry-run checklist (do this on the pad)

[ ] n = 0
[ ] n = 1
[ ] target smaller than all
[ ] target larger than all
[ ] target equals first and last
[ ] even and odd n

If any case stalls the loop on paper, fix the template before coding.

Freeze recovery

Delete the buggy loop; rewrite from the chosen template
Print (mentally) left, right, mid for three iterations
State the predicate in words again
If duplicates confuse you, solve the unique-elements version first and note the limitation

Talk track:

“I’m going to lock a half-open lower-bound template so left is always the first feasible index.”

Practice plan

Session	Focus
1	Classic index search + missing target
2	Lower/upper bound variants
3	Answer-space (Koko / capacity style)
4	Rotated array with spoken half choice

Soft practice note

Boundary bugs vanish with slow narration more than with more LeetCode reps alone. If you want a Chrome side panel to practice saying the template and dry-running edges under time pressure, Luna Interview is built for that rehearsal. Use it for calm correctness—not to skip understanding monotonicity or to violate interview rules.

Day-of checklist

[ ] Monotonicity spoken
[ ] Template chosen (closed vs half-open)
[ ] Mid formula safe
[ ] Updates always shrink the range
[ ] Ends and empty cases dry-ran
[ ] Return value meaning clear

Master the boundaries—the binary search interview is mostly that.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.