skip to content

In a binary search over a sorted page index, which invariant about the current bounds makes the exit answer correct?

level: seniorimportance: must knowfreq 54%

answer

  1. it is an implication, one direction
  2. the window is the only possible place
  3. discards justified by sort order
  4. empty window proves absence
  5. lo becomes the insertion point

basics

~20 s

The window invariant: if the target key occurs in the index at all, its position lies inside the current bounds. Each comparison discards only the side the sort order proves cannot hold it, so an empty window at exit proves absence.

solid answer

~50 s

Search a sorted index of page start-keys with a half-open window `[lo, hi)`. The invariant is one implication: *if the target key is present, its position is in `[lo, hi)`* — equivalently, every position below `lo` holds a smaller key and every position at or above `hi` holds a key at least as large. Initialization is the full range. Maintenance is where sortedness earns its keep: when `index[mid] < key`, sortedness makes every position up to `mid` too small, so setting `lo = mid + 1` cannot discard the target; otherwise `hi = mid` is safe for the mirror reason. At exit `lo == hi`, so the window is empty; by the invariant the key is absent, and `lo` is where it would belong. The implication runs one way only — an empty window proves absence, never presence.

code

pseudocode · 16 lines
pseudocode
lo <- 0
hi <- n                       # half-open window [lo, hi)

# INVARIANT: every position below lo holds a key < target,
# every position at or above hi holds a key >= target;
# so if target is present, its position is in [lo, hi).
while lo < hi do
    mid <- lo + (hi - lo) / 2          # floor division, lo <= mid < hi
    if index[mid] < target then
        lo <- mid + 1                  # mid ruled out by sortedness
    else
        hi <- mid                      # mid still a candidate

# exit: lo = hi, window empty.
# lo is the insertion point; target present only if
# lo < n and index[lo] = target

go deeper

for a junior

Recall that the loop keeps a window of still-possible positions and throws away the half the ordering rules out, rather than scanning every entry.

for a middle

State the invariant as an implication and show which sortedness fact justifies each of the two updates, including why one bound moves past the midpoint and the other does not.

for a senior

Use the invariant as the debugging tool: when a search loop misbehaves, decide whether the symptom is a wrong answer (invariant) or a spin (measure), and name the branch responsible.

for a principal

Set the convention. Half-open windows, one stated invariant per search-shaped loop, and a postcondition that says which occurrence is wanted remove a whole family of off-by-one defects from a codebase.

## The setting A sorted index lists the first key of each page, ascending, with no duplicates. Given a lookup key you want the page that would contain it, or a definite "not present". The loop keeps two bounds and shrinks them. Everything interesting about the loop is in what those two bounds are claimed to mean. ## The invariant is an implication, not an equality With a half-open window `[lo, hi)` the invariant is: > If the target key appears in the index, its position is in `[lo, hi)`. Spelt out over the index, the same claim reads: every position strictly below `lo` holds a key smaller than the target, and every position at or above `hi` holds a key at least as large. That phrasing is the one to carry into maintenance, because it is what each branch actually re-establishes. The direction matters and is the most common thing candidates get backwards. The invariant does **not** say the target is in the window; it says the window is the only place it could be. That asymmetry is exactly what licenses the exit conclusion "not found" from an empty window, and it is why an empty window never proves the key is present somewhere else. ## The three obligations on this loop 1. **Initialization** — `lo = 0`, `hi = n`. There is no position below `0` or at/above `n`, so both halves hold vacuously and the window is the whole index. 2. **Maintenance** — pick `mid` inside the window and compare. - `index[mid] < key`: by sortedness every position up to and including `mid` holds a key smaller than the target, so no occurrence can be there. Setting `lo = mid + 1` keeps the implication true. - `index[mid] >= key`: every position from `mid` upward holds a key at least as large, so any occurrence is at or below `mid`. Setting `hi = mid` keeps it true. 3. **Exit** — the guard `lo < hi` fails, so `lo == hi` and the window is empty. Combined with the invariant: if the key were present its position would be inside an empty range, which is impossible, so it is absent. `lo` is then the insertion point — the first position holding a key at least as large. ## Why the update must be asymmetric | Branch | Safe update | Why | Effect on the window size | |---|---|---|---| | `index[mid] < key` | `lo = mid + 1` | `mid` itself is ruled out, so excluding it is sound | Strictly smaller | | `index[mid] >= key` | `hi = mid` | `mid` is still a candidate; `hi` is exclusive, so it stays in | Strictly smaller | The classic bug is writing `lo = mid` in the first branch. Notice what it does and does not break: the invariant still holds — keeping a position you already know is too small only weakens the claim, it does not falsify it. What breaks is termination. When the window has size one, `mid` equals `lo`, so `lo = mid` leaves both bounds untouched and the loop spins with a perfectly valid invariant. That is the cleanest demonstration there is that the invariant and the termination argument are separate obligations. ## Termination of this loop The measure is the window size `hi - lo`. With `lo < hi`, the chosen `mid = lo + (hi - lo) / 2` using floor division satisfies `lo <= mid < hi`. The first branch raises `lo` to `mid + 1`, which is strictly greater than `lo`; the second lowers `hi` to `mid`, which is strictly less than `hi`. Either way `hi - lo` strictly decreases, and it is bounded below by zero — so the loop stops. Both branches also shrink the window to at most half plus rounding, but that fact is about how *fast* it stops, not whether it does. ## What people get wrong under pressure - Stating the invariant as "the key is between `lo` and `hi`", which is false as soon as the key is absent, and then being unable to explain why "not found" is sound. - Mixing a half-open window with a closed-window guard, or the reverse, so the last candidate is either checked twice or never checked. Pick one convention and let the invariant enforce it. - Computing the midpoint in a way that can exceed the representable range of the index type; the `lo + (hi - lo) / 2` form avoids the sum overflowing while keeping the same value. - Assuming the answer is unique when the index may hold repeated keys. The invariant above finds the first position that is at least the target; "any occurrence" needs a different, explicitly stated postcondition. ## The transferable lesson The invariant of a shrinking-window search is the shape to reuse: *the answer, if it exists, is inside the window*. It applies to any loop that discards candidates — provided every discard is justified by a property strong enough to rule the discarded side out, and the window strictly shrinks each pass.

  • If the first branch is written as lo = mid, which obligation breaks?
    Termination, not the invariant. Keeping a position already known to be too small only weakens the claim, so the implication stays true. But on a window of size one, `mid` equals `lo`, so neither bound moves, the measure `hi - lo` stops decreasing and the loop spins — with a valid invariant the whole time.
  • Why does an empty window prove the key is absent?
    Because the invariant is the implication "if present, then inside the window". Contraposing it: not inside the window implies not present. An empty window contains no position, so no position can hold the key. The reverse reading — "the key is in the window" — would be false whenever the key is absent, and would prove nothing at exit.
  • What changes if the index may contain repeated keys?
    The postcondition has to say which occurrence you want, and the invariant must match it. The form above lands on the first position whose key is at least the target, so it finds the earliest occurrence. Wanting the last one needs the mirror invariant and the mirror asymmetry in the two updates.

saying these in an interview costs you the question

  • States the invariant as "the key lies between the bounds"
  • Cannot say why an empty window means not found
  • Moves both bounds to mid and expects the loop to shrink
  • Mixes a closed window with a half-open guard
  • Claims the invariant breaks when the update is off by one
  • Says sortedness is only needed for the final comparison