In a leftmost-occurrence binary search, why does a match record the index and keep searching left?
answer
- a hit answers one question and opens another
- sorted means equal keys are contiguous
- nothing right of a match can be smaller
- what stays true at every loop test
- the interval must exclude mid to shrink
basics
~20 sA match proves the target exists there, but a smaller matching index can only lie strictly left. So the loop saves the hit as its best candidate, discards the midpoint and everything right of it, and continues.
solid answer
~50 sEquality carries two facts, and the loop must use both. First, `mid` is a valid answer, so it is saved as the best candidate seen so far. Second, because equal keys are contiguous in a sorted array, any *better* answer — a smaller matching index — must be strictly left of `mid`, so the whole right side including `mid` is dead. That gives the invariant: the saved candidate is the smallest matching index found so far, and every matching index smaller than it still lies inside `[lo, hi]`. When the interval empties, no smaller match can exist, so the candidate is the leftmost occurrence. The shrink must be `hi = mid - 1`, not `hi = mid`: in a closed-interval loop, `mid` can equal `lo` and `hi`, and re-including it makes the interval stop shrinking.
code
pseudocode · 13 lineslo = 0
hi = length(a) - 1
best = NOT_FOUND
while lo <= hi:
mid = lo + (hi - lo) / 2 // floor division
if a[mid] == target:
best = mid // valid answer; a better one is left
hi = mid - 1
else if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return bestgo deeper
Be ready to explain in words why the search does not stop at a match: the index found is valid, but an earlier one might exist, and it can only be to the left. Knowing that much beats reciting the code.
Expect to write the loop and defend it. Name the invariant, show each branch preserves it, and explain why the equality branch must move the pointer past the midpoint or the loop can spin on a one-element interval.
Show how you make this class of code trustworthy rather than lucky: the four checks (empty input, all-duplicates, run at index 0, run at the last index) and a preference for the shape whose termination argument is one line.
Own the build-versus-reuse call. Hand-written boundary searches are a recurring bug source across a codebase; standardising on one reviewed helper with a stated contract usually beats letting each team roll its own variant.
## Reading the loop as an invariant, not as steps Hand-written binary search variants are notoriously easy to get almost right. The way to make them reliable is to stop thinking "where do the pointers move" and start thinking "what is true every time the loop test is evaluated". For the record-and-shrink leftmost search over a closed interval `[lo, hi]`, three statements hold at the top of every iteration: 1. **Candidate soundness.** If `best` has been set, then `a[best] == target`. 2. **Candidate optimality-so-far.** No index smaller than `best` outside `[lo, hi]` matches the target. 3. **Search-space completeness.** Every matching index smaller than `best` (or every matching index at all, if `best` is unset) lies inside `[lo, hi]`. Together these say: the answer is either `best` or something inside the shrinking interval. When the interval empties, the second disjunct is gone, so `best` — set or unset — is the final answer. ## Why equality shrinks instead of returning When `a[mid] == target`: - `mid` satisfies invariant 1 immediately, so setting `best = mid` is sound. - Because the array is sorted, all copies of the target are contiguous. Every index greater than `mid` is therefore either another copy (a *worse* answer for a leftmost query) or a strictly greater key. Either way, nothing to the right can improve on `mid`. - The only place a better answer can hide is strictly left. So `hi = mid - 1` preserves invariant 3 while making progress. That is the entire difference from a plain search. A plain search treats equality as "done"; a boundary search treats it as "good, and now the question is whether there is a better one". ## Why `mid - 1` and not `mid` The closed-interval loop runs while `lo <= hi`, so the interval can legitimately hold a single element with `lo == hi == mid`. If a match then set `hi = mid`, the interval would be unchanged and the loop would spin forever. Discarding `mid` is safe precisely because it has already been recorded in `best` — the information is not lost, only the index is. This is the general rule for closed-interval binary searches: **every branch must exclude `mid`**, because `mid` is always inside the current interval and re-including it permits a no-op iteration. The mirrored search for the last occurrence has an analogous termination requirement of its own, arising from the other end of the interval. ## Cost The interval's size goes from `hi - lo + 1` to at most half of that on every iteration, in all three branches. So the loop runs about `floor(log2 n) + 1` times regardless of how many matches exist, and the total is O(log n) comparisons and O(1) extra space. Removing the early return does not change the asymptotic bound — it only removes a best case that was never guaranteed. Even in the extreme where **every** element equals the target, the loop takes logarithmically many iterations, not one per duplicate. ## The three-branch shape versus the two-branch shape There are two common ways to write this: - **Record and shrink** (three branches: `==`, `<`, `>`), as above. Its virtue is that it is self-documenting — the equality branch says out loud "candidate found, keep going" — and "not found" is expressed by `best` never being written. - **Collapse to a single index** (two branches, loop while `lo < hi`), which converges on one position and then checks whether it matches. It is shorter, but the rounding of the midpoint becomes load-bearing, and the post-loop check is easy to get wrong on empty arrays. For an interview, the record-and-shrink form is usually the better thing to write on the board: it has no off-by-one in the midpoint, its termination is obvious (`hi - lo` strictly decreases in every branch), and its absence handling needs no post-loop index validity check. When asked to "prove it works", state the three invariants above and show each branch preserves them. ## What to check when reviewing one - Does every branch move a pointer past `mid`? - Is the candidate written *before* the interval shrinks? - Does an empty input skip the loop entirely and return the sentinel? - Does an array consisting entirely of the target return index 0? Those four checks catch nearly every hand-written boundary-search bug.
- State the loop invariant precisely.At the top of every iteration: if the candidate is set, it indexes a matching element; no smaller matching index lies outside `[lo, hi]`; and every matching index smaller than the candidate lies inside `[lo, hi]`. Each branch preserves all three, and each branch strictly shrinks the interval. On exit the interval is empty, so no smaller match exists and the candidate — set or unset — is the final answer.
- What happens if the equality branch uses hi = mid instead of hi = mid - 1?In a closed-interval loop the interval can shrink to a single element with `lo == hi == mid`. Setting `hi = mid` then leaves the interval unchanged and the loop never terminates. Excluding `mid` is safe because it was already recorded as the candidate, so discarding the index loses no information. The general rule: in a `lo <= hi` loop, every branch must move a pointer past `mid`.
- How many iterations does this run when every element equals the target?Logarithmically many — about `floor(log2 n) + 1`. Every equality hit still halves the interval, so a fully duplicated array is not a bad case for this loop at all; it simply takes the equality branch every time and walks straight down to index 0. That is the whole point of shrinking rather than scanning: the cost is insensitive to how many duplicates there are.
saying these in an interview costs you the question
- Says the loop must return as soon as it finds a match
- Uses hi = mid in a closed-interval loop and calls it equivalent
- Claims removing the early return makes it O(n)
- Records the candidate after shrinking, then reads a stale index
- Cannot state what is true at the top of the loop