In binary search, what changes when you use a half-open range [lo, hi) instead of a closed [lo, hi]?
answer
- what does the upper bound actually name
- one past the end versus the last position
- count the elements in each form
- which discard step keeps the midpoint
- how each form spells an empty range
basics
~20 sFour things move together: the initial upper bound (one past the end versus the last index), the loop condition, which shrink step keeps the midpoint, and how an empty range is spelled. Never mix halves of the two conventions.
solid answer
~50 sIn the closed form the upper bound is a real position: it starts at the last index, the loop runs while `lo <= hi`, both branches exclude the midpoint (`lo = mid + 1`, `hi = mid - 1`), and the range is empty when `lo > hi`. In the half-open form the upper bound is one past the last candidate: it starts at the size, the loop runs while `lo < hi`, and the discard step is `hi = mid` — the midpoint is excluded automatically because the upper end is exclusive. The range is empty exactly when `lo == hi`, which is also where the sought value would belong, so no out-of-range sentinel is needed and the size is `hi - lo` with no plus-one. Both are correct; the bugs come from mixing them — an upper bound of the size with `lo <= hi` lets the midpoint reach one past the end.
go deeper
Be ready to say what the upper bound means in each convention — the last candidate versus one past it — and to initialize it accordingly. Knowing the range size formula for each is a quick way to check yourself.
Explain all four coupled decisions and why the discard step differs: an exclusive upper bound already excludes the midpoint, so the minus-one that is correct in one form throws away an extra candidate in the other.
Diagnose the mixing bugs from a symptom: a range error only when the sought value is larger than everything, or a silent miss only when the answer sits at the last position. Say which mixed pair produces which.
Pick a house convention and justify it from the codebase rather than taste — slicing and splitting code, unsigned index types, and whether loops must return early on a match — then make the range's meaning an explicit comment so the other three decisions follow.
## Two ways to name the same set of candidates A search range is a set of still-possible positions, and there are two standard ways to write one down. **Closed, `[lo, hi]`.** Both endpoints are real candidate positions. The range holds `hi - lo + 1` elements. It is empty when `lo > hi`. **Half-open, `[lo, hi)`.** The lower endpoint is a candidate; the upper endpoint is one past the last candidate. The range holds `hi - lo` elements. It is empty when `lo == hi`. Both describe the same searches. What differs is a package of four decisions that must be made consistently, and the failure mode is always the same: taking two decisions from one package and two from the other. ## The two packages, side by side | decision | closed `[lo, hi]` | half-open `[lo, hi)` | | --- | --- | --- | | initial bounds | `lo = 0`, `hi = n - 1` | `lo = 0`, `hi = n` | | loop condition | `while lo <= hi` | `while lo < hi` | | discard the upper half | `hi = mid - 1` | `hi = mid` | | discard the lower half | `lo = mid + 1` | `lo = mid + 1` | | empty range | `lo > hi` | `lo == hi` | | size of range | `hi - lo + 1` | `hi - lo` | Read the discard column carefully, because it is where the conventions really differ. In the closed form the upper bound is inclusive, so to throw the midpoint away you must step past it: `hi = mid - 1`. In the half-open form the upper bound is already exclusive, so `hi = mid` throws the midpoint away by itself — writing `hi = mid - 1` there would discard the position just below the midpoint as well, and that position may hold the answer. Same-looking line, opposite meaning. ## Why half-open tends to be the calmer convention Three small properties add up: 1. **The size is a subtraction, not a subtraction plus one.** Off-by-one errors love the plus-one. Nested and recursive range code stays readable when a sub-range of `[lo, hi)` split at `mid` is exactly `[lo, mid)` and `[mid, hi)` — the two pieces share a boundary and no index is written twice. 2. **The empty range is representable without a sentinel.** In the closed form, an empty range at the front of the collection is `lo = 0`, `hi = -1`, which means the bound variable must be able to hold a value that is not a valid position. With an unsigned index type that is an outright hazard: decrementing zero wraps to an enormous value. 3. **Termination leaves a meaningful value.** The `while lo < hi` loop ends with `lo == hi`, a single well-defined position — the place the sought value sits if it is present, or the place it would belong if it is not. Nothing extra needs computing to answer "where does this go?". The closed form's compensating virtue is that both branches exclude the midpoint, so the range shrinks unconditionally and the loop cannot hang no matter how the midpoint rounds. It also handles an exact match naturally by returning from inside the loop. **Conventions across ecosystems.** This is a language-design choice as much as an algorithm one: range-and-slice notation in Python, Go and Rust is half-open by default (the upper end is excluded), whereas Ruby and Pascal-descended languages offer inclusive ranges as a first-class form. Nothing about correctness follows from either choice — it just means engineers arrive at a search loop already carrying a habit, which is a real argument for making the convention explicit in a codebase instead of assuming it. ## The mixing bugs, concretely - **Bound set to `n`, condition `lo <= hi`.** Reachable state: everything compares smaller than the sought value, so `lo` climbs to `n` while `hi` stays `n`. The condition still holds, the midpoint is computed as `n`, and the code reads one past the end. On a checked runtime that is a raised range error; on an unchecked one it is a read of whatever is next in memory. - **Bound set to `n - 1`, condition `lo < hi`.** The last position is never examined; a value present only at the end is reported missing. This one is worse than a crash because it is silent and passes any test whose data does not put the answer last. - **Half-open range with `hi = mid - 1`.** Discards the midpoint *and* its left neighbour, so the search can step over the answer entirely. Again silent. - **Closed range with `hi = mid`.** The midpoint stays in the range on the discard path, so on a two-candidate range the bounds can stop moving and the loop hangs. Every one of these is a two-line diff to fix and a one-line invariant to prevent. Which is the real lesson: the convention is not the interesting part, the **consistency** is. Write the range's meaning as a comment above the loop — "candidates are the positions in `[lo, hi)`" — and every one of the four decisions follows from it mechanically. ## What to say when asked which one to use Say that you pick one and apply it everywhere, then defend the pick on the codebase rather than on aesthetics: half-open if the surrounding code slices and splits ranges (the shared-boundary property pays off, and unsigned index types stay safe), closed if the loop must return early on an exact match and you value the unconditional shrink. What you should not do is claim one is correct and the other wrong, or switch between them within one file.
- A search initializes the upper bound to the collection size but loops while lo <= hi. What breaks and when?When the sought value compares larger than everything, `lo` climbs to the size while the upper bound stays there; the condition still holds, so the loop computes a midpoint equal to the size and reads one past the end. It fails only on the everything-is-smaller path, which is why it survives casual testing and then raises a range error — or silently reads adjacent memory — in production.
- Why is hi = mid - 1 wrong in a half-open range but right in a closed one?In a closed range the upper bound is a real candidate, so discarding the midpoint requires stepping past it. In a half-open range the upper bound is already exclusive, so `hi = mid` discards the midpoint by itself; writing `hi = mid - 1` there also discards the position immediately below the midpoint, which may be the answer. The search then reports a present value as missing, with no error.
- What does the half-open loop leaving lo equal to hi tell you?That the candidate range is now empty, and that the surviving position is where the sought value sits if present and where it would belong if absent. That is why the convention needs no negative sentinel and why callers can use the result directly as a placement position rather than computing it separately.
Fence posts versus fence panels: a closed range counts posts, so both ends are real objects; a half-open range counts panels, so the far end is the post just past the last panel.
saying these in an interview costs you the question
- Says the conventions differ only in the initial upper bound
- Pairs an upper bound of the size with an inclusive loop condition
- Claims a half-open range needs a negative not-found sentinel
- Computes the half-open range size as hi minus lo plus one
- Argues one convention is universally correct and the other broken