What does binary search return on a ledger sorted by id when you probe by amount?
answer
- What does the algorithm actually verify?
- Ordering key versus comparison key
- It never compares two neighbours
- Wrong half discarded, loop still terminates
- Confident answer, no exception
basics
~20 sNothing signals an error. The file is ordered by id but the search compares amounts, so each halving step discards the wrong half and returns an arbitrary index or a false "not present" — silent garbage, not an exception.
solid answer
~40 sBinary search never checks its precondition — it simply assumes that the comparison at the midpoint tells it which half holds the target. If the records are ordered by id but the comparison is on amount, that answer is noise, so the search discards a half that may contain the target and returns either `NOT_FOUND` for a record that is present or an index pointing at the wrong row. There is no exception and no ordering check, because the algorithm never compares two neighbouring elements — it only ever looks at about `log n` of them. The bug is deterministic per input, which makes it worse: the same wrong index comes back every run, and downstream code that treats the result as an insertion point will happily write corrupt data.
code
pseudocode · 12 lines// records r[0..n-1] are ordered by r[i].record_id
lo = 0
hi = length(r) - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if r[mid].amount == target:
return mid
if r[mid].amount < target:
lo = mid + 1 // discards a half chosen by a meaningless comparison
else:
hi = mid - 1
return NOT_FOUNDgo deeper
Be ready to say plainly that binary search does not check its input: wrong order gives a wrong answer with no error. Know that the ordering key and the comparison key must be the same key.
Explain the mechanism — the midpoint comparison is the oracle deciding which half to discard, and it is only truthful when the data is ordered on the probed key. Explain why validating it per query costs as much as scanning.
Show how you catch this in review and in tests: derive ordering and comparison from one key function, assert the invariant where the data is produced, and property-test the search against a linear scan rather than against a hand-picked value.
Own the systemic version — a silent wrong index that becomes a written insertion point is a data-corruption class, not a bug. Decide where the ordering contract is enforced and who owns it when the producer of the file is another team.
## What the midpoint comparison is actually buying Binary search maintains a range `[lo, hi]` and repeatedly asks one question: is the target above or below the element sitting at the midpoint? Answering it lets the algorithm discard half the range, which is where the `O(log n)` comes from. The entire method rests on that single comparison being a **truthful oracle** — "everything on this side of `mid` is smaller, everything on that side is larger". Sortedness on the probed key is exactly the property that makes the oracle truthful. Nothing else in the algorithm defends it. So the precondition is not "the data is sorted". It is sharper than that: **the data must be ordered by the same key the comparison uses**. A ledger physically ordered by transaction id is perfectly sorted, and completely useless to a search that compares amounts. Every probe returns a truthful fact about that one row and a meaningless conclusion about the half you throw away. ## Why it is silent rather than loud Three properties combine into the worst kind of bug: - **No validation.** Checking sortedness costs `O(n)` — the same order as the linear scan binary search exists to avoid — so no implementation does it on the hot path. - **No adjacent comparisons.** The search only ever compares the target against elements it lands on. Over a million rows it touches roughly twenty of them. It never sees two neighbours side by side, so a violated order is invisible to it by construction. - **Guaranteed termination.** The range shrinks every iteration regardless of what the comparisons say, so the loop always ends — with an answer that looks exactly like a legitimate answer. The outcome is a plausible index or a plausible "absent". If the caller uses the returned position as an *insertion point* — to merge two files, to deduplicate, to splice a correction into the ledger — the garbage index becomes garbage data, and the original defect is now several systems away from where it will be noticed. There is also a blunt way to see how little the search can recover: over `n` rows it examines at most about `log2(n)` of them. On a million-row ledger that is roughly twenty positions out of a million. A present record is reported found only if it happens to sit on that short probe path. In unordered data, that is close to a lottery. ## Why the tests passed This is the part that gets people in review. Two very common test shapes pass on unordered input: - **A test that searches the middle row.** The first probe is *always* the midpoint of the range, before any comparison has had a chance to mislead anything. Look up the element at index `n/2` and it is found immediately, on any input whatsoever, sorted or shuffled. - **A three- or four-row fixture.** With `n` that small the probe path covers most of the array, so the search stumbles onto the answer often enough to look correct. The property only breaks down as `n` grows — which is to say, in production. A test that would actually catch it looks different: generate random data, run the binary search and a plain linear scan over the *same* input, and assert they agree — for values that are present, values that are absent, duplicates, and the first and last rows. That is a property test, and it fails immediately when the ordering key and the probe key disagree. ## Reviewing for it When you see a binary search in a diff, read two things and check that they are the same expression: **what ordered the data** and **what the comparison probes**. They are usually far apart in the code — the order comes from an upstream export, a query, or a file the team assumes is "sorted"; the comparison is right there in the loop. The strongest fix is structural rather than a comment: derive the ordering and the comparison from one shared key function, so they cannot drift apart, and assert the invariant once at the boundary where the data is produced, where an `O(n)` check is amortized over every query that follows. The misconception to retire is "if the input is wrong, it will fail". Binary search does not fail on bad input. It answers confidently, and it is wrong.
- Why can't the implementation just detect that its input is out of order?Detecting it means comparing adjacent elements across the whole range, which is `O(n)` — the exact cost binary search exists to avoid, so paying it per query would erase the benefit. A search that touches roughly `log n` elements can never see the violation. The check belongs once at the boundary that produces the data, where its cost is amortized over every later query.
- A test looks up the middle record and passes. Why does that prove nothing?The midpoint is the first position probed, before any comparison can steer the search wrongly, so that one value is found on any input at all — ordered or shuffled. It tests that the loop runs, not that the precondition holds. A property test comparing the search's result against a linear scan over random inputs, including absent values and the two ends, is what actually catches it.
- What is the downstream damage if the caller uses the returned position as an insertion point?The wrong index gets written rather than merely read. Splicing a record at a bogus position corrupts the order for every future search, so one bad lookup degrades the whole file, and deduplication or merge logic built on that index silently drops or duplicates rows. The corruption then surfaces far from the search that caused it.
It is like looking someone up in a staff list ordered by employee number while flipping pages based on their surname: every page you open is real, and every decision about which way to flip is a coin toss.
saying these in an interview costs you the question
- Says binary search throws or errors on unsorted input
- Says it degrades to a linear scan but stays correct
- Thinks the algorithm validates order before searching
- Assumes 'the file is sorted' without asking sorted by what
- Believes a passing unit test proves the precondition holds
- Treats a returned index as safe to use as an insertion point