Why does a plain binary search return an arbitrary index when the sorted array holds duplicate keys?
answer
- think about when the loop stops
- equal keys form one contiguous run
- which member did the midpoint hit
- returning on the first match ends the hunt
- leftmost means keep going after a hit
basics
~20 sA plain binary search returns the moment a midpoint matches, so which member of a run of equal keys comes back depends only on where the splits fell. The leftmost occurrence requires searching on after a hit.
solid answer
~50 sIn a sorted array all copies of a value sit in one contiguous run. A plain binary search halves the interval and returns as soon as `a[mid] == target`, so it reports whichever index of that run a midpoint landed on first — determined by the array's length and the split geometry, not by anything meaningful about the data. The result is deterministic but unstable: insert one unrelated element earlier in the array and the same query can report a different index. To get the first occurrence you change what equality means to the loop: instead of terminating the search, a match records a candidate and shrinks the interval leftward, so the loop keeps hunting for an even smaller matching index. The mirrored change gives the last occurrence, and both stay O(log n) because the interval still halves every iteration.
go deeper
Be ready to say that equal keys sit in one contiguous run and that a plain search stops at whichever member a midpoint hit first. Name the fix in one sentence: on a match, remember the index and keep searching the side you want.
Explain why the interval still halves once the early return is removed, so the bound stays logarithmic. Show that the answer is deterministic yet arbitrary — a single inserted element elsewhere can change which index comes back.
Demonstrate that you treat the arbitrary hit as a correctness hazard, not a curiosity: sample data hides it, production skew exposes it. Say how you would test it — arrays whose entire content is the target, runs at both ends, runs of length one.
Own the interface question: expose a boundary or range API rather than a find-any primitive, so callers cannot accidentally depend on an unspecified index. Unspecified return values become de-facto contracts the moment someone builds on them.
## The setup Binary search assumes a sorted sequence with random access. Sortedness has a consequence people skip past: **every copy of a given value occupies one contiguous run of indices**. If a value appears at index 5 and at index 9, it also appears at 6, 7 and 8 — there is nowhere else it could live. So "where is this value?" is not one index; it is an interval `[first, last]`. A plain binary search answers a different question than the one a boundary problem asks. It answers *does this value exist, and at some index where?* — a membership test that happens to hand back a witness. ## Why the witness is arbitrary The classic loop compares three ways: - `a[mid] < target` — the answer, if any, is strictly right; move `lo`. - `a[mid] > target` — the answer is strictly left; move `hi`. - otherwise — equal, so return `mid`. That third branch is the whole story. The moment any midpoint falls inside the run, the search stops. Which member of the run that is depends on the sequence of midpoints, and the sequence of midpoints depends on the array's length, the run's position, and the rounding rule for the midpoint — none of which the caller controls or cares about. Concretely: take a sorted array of read positions where the marker value occupies indices 5 through 9. The first midpoint of a 20-element array is index 9 or 10 depending on rounding. Land on 9 and the search returns 9 — the *last* occurrence, which happens to be right for a "last" query and wrong for a "first" one, by luck. Prepend a single smaller element and every midpoint shifts; now the same query may return 7. The result is **deterministic but not meaningful**. That distinction matters when a test passes on your sample data and the behaviour changes when the dataset grows. ## What a first-occurrence search does differently The fix is not a post-processing step; it is a change to what equality means inside the loop. When `a[mid] == target`, you have learned two things: 1. The target exists, and `mid` is a valid answer — so remember it. 2. Any *smaller* matching index must be strictly left of `mid` — so the right half, including `mid`, is now useless. So instead of returning, record `mid` as the best candidate so far and shrink the interval to the left half. The loop runs to exhaustion; whatever candidate survives is the leftmost occurrence. The mirror image — record and shrink rightward — yields the last occurrence. | variant | on `a[mid] == target` | terminates when | |---|---|---| | plain search | return `mid` | any match found | | first occurrence | record `mid`, search left | interval empty | | last occurrence | record `mid`, search right | interval empty | ## The cost does not change A common worry: "if it doesn't stop early, isn't it slower?" Asymptotically, no. The interval still halves on every iteration — a match now shrinks the interval instead of ending the loop, but it still shrinks it. Both variants run in O(log n) comparisons. What you lose is the *lucky* early exit, which was never something you could count on anyway: a plain search's best case is one comparison, but its bound is logarithmic either way. What you must not do is the tempting shortcut: find any match, then walk left until the value changes. That walk costs one step per element in the run, so its cost is proportional to how many duplicates you have — the exact quantity that made you want a boundary search in the first place. ## Preconditions worth saying out loud - **The array must be sorted by the key you are searching.** Duplicates are contiguous only because of sortedness; on unsorted data the whole idea collapses. - **Absence must be representable.** With the record-and-shrink shape, no candidate is ever recorded when the target is missing, so the "not found" answer falls out of the loop naturally rather than needing an extra check. - **Equal keys must be interchangeable for your purpose.** If the elements carry payloads and you need a *specific* one of several equal keys, the boundary index is where you start, not where you finish.
- Does dropping the early return make the search slower?Not asymptotically. A match now shrinks the interval instead of ending the loop, so the interval still halves every iteration and the bound stays O(log n). You give up a lucky early exit that was never guaranteed — a plain search's best case is one comparison, but its worst case was already logarithmic. In exchange the answer becomes well-defined rather than dependent on where midpoints happened to fall.
- Why can't you just walk left from whatever index the plain search returned?Because the walk costs one step per duplicate. If the run has k equal keys, the walk is O(k), and k can be a large fraction of the array — precisely the case where boundary searches matter. It turns a logarithmic query into a linear one on exactly the inputs that motivated it. A second binary search costs another O(log n) and is insensitive to how long the run is.
- How does the loop report that the target is absent entirely?In the record-and-shrink shape, the candidate slot is only ever written inside the equality branch. If the target never appears, the loop exits with the slot untouched and you return the sentinel. No extra bounds check or post-loop comparison is needed, which removes a common source of off-by-one bugs in hand-written variants.
Looking up a headword that a dictionary prints on several consecutive lines: opening the book at one of those lines proves the word is there, but says nothing about where its entry begins.
saying these in an interview costs you the question
- Claims binary search always lands on the first match
- Says duplicates make binary search incorrect
- Thinks the returned index depends on the target's value
- Proposes scanning left afterwards and still calls it O(log n)
- Assumes equal keys can be scattered across a sorted array