In a sorted array, what does a lower bound search return when the target value is absent?
answer
- a miss here is not a failure
- the search still answers with a position
- think about where the value would slot in
- first element not smaller than the target
- valid answers run from 0 through n
basics
~20 sA lower bound search returns the first index whose element is greater than or equal to the target. For an absent key that index is exactly where the value would be inserted to keep the array sorted. It never reports failure.
solid answer
~40 sA lower bound search answers a positional question rather than a yes/no one: it returns the smallest index `i` such that `a[i] >= target`. When the target is present that is its first occurrence; when the target is absent it is the gap the value would slide into, so the array stays sorted — the insertion point. If every element is smaller than the target, the answer is `n`, the array length: a legal one-past-the-end insertion position, not an error. That is the key difference from an exact-match search, which has to invent a miss sentinel. Because the result is a position rather than a verdict, presence is a separate check: `i < n && a[i] == target`. The search itself is O(log n) comparisons and needs random access plus sorted order.
go deeper
Be ready to state the definition crisply — first index whose element is at least the target — and to name the two edge answers, 0 and n. Screeners mostly want to hear that an absent key still gets a position.
Explain why the result is a position rather than a verdict, and show the two-part presence check. An interviewer expects you to connect the returned index to keeping the array sorted after an insert.
Show the production angle: the one-past-the-end return is a real out-of-bounds hazard in calling code, and bucketing values into ranges is the common case where no exact match ever occurs.
Own the interface argument: a search that answers with a position composes into bucketing, insertion and range queries, while one that answers with a boolean forces every caller to re-derive the position.
## Two different questions Plain binary search asks: **is this value here?** A boundary search asks: **where does this value belong?** The second question is strictly more useful, and it is the one interview problems almost always want. The lower bound of a target in an array sorted ascending is defined as: > the smallest index `i` in `0..n` such that `a[i] >= target`, or `n` if no such index exists. Read it as *first index that is not below the target*. Nothing in that definition requires the target to be present. That is the whole point. ## The insertion point When the target is absent, the lower bound is the position at which you could insert the value and leave the array sorted. Everything before that index is strictly smaller; everything from that index on is strictly larger. Inserting between those two groups preserves order, which is exactly the definition of an insertion point. A worked example from a fee schedule. Tier thresholds, sorted ascending, are the minimum amounts at which each tier starts: ``` index: 0 1 2 3 4 threshold: 0 500 2000 10000 50000 ``` A transaction of 2000 is present at index 2 — the lower bound is 2. A transaction of 7500 is absent; the first threshold that is at least 7500 is 10000 at index 3, so the lower bound is 3. That tells you 7500 sits *between* the tier starting at 2000 and the tier starting at 10000, which is precisely the information the pricing code needs — and no exact match ever occurs for a realistic amount. ## The two edges The returned index ranges over `0..n` inclusive — `n + 1` possible answers, not `n`. Both endpoints are meaningful and both get fumbled: - **0** — every element is at least the target; the value belongs before everything. For an amount of -5 against the table above, the answer is 0. - **n** — every element is strictly smaller; the value belongs after everything. For an amount of 90000, the answer is 5, the array length. This is *not* an error and *not* a miss code. It is a valid insertion position that happens to be one past the last element. Callers who immediately read `a[i]` without checking `i < n` are reading out of bounds, and that is the single most common bug built on top of a correct bound. ## Presence is a separate question Because the result is always a position, it carries no information about whether the target was found. The check is two-part and both halves matter: ``` i = lowerBound(a, target) found = (i < length(a)) and (a[i] == target) ``` Omit the range test and you dereference past the end when the target exceeds everything. Omit the equality test and you claim every absent key is present. Candidates who assert "the search returns -1 when the key is missing" have imported the exact-match convention into a boundary search, where it does not apply — a bound has no miss to signal. ## Why a bound rather than an exact match Three everyday jobs are boundary jobs, not membership jobs: 1. **Bucketing a value into ranges** — the fee-tier case above. Membership is irrelevant; the gap is the answer. 2. **Maintaining a sorted collection** — you need the position before you can insert. 3. **Range queries** — the bounds of the target range delimit the slice you want, whether or not the endpoints themselves exist. All three are unanswerable with a boolean. Once you internalise that a boundary search returns a *place*, the family of variants stops looking like a pile of tricky loops and starts looking like one template with a swappable comparison. ## Preconditions and cost The array must be sorted by the same ordering the comparison uses, and the access pattern must be random access — halving a range is meaningless if reaching the midpoint costs a walk. The cost is O(log n) comparisons and O(1) extra space in the iterative form. Note carefully what that cost covers: *finding* the position. Actually placing an element there in an array is a separate, much more expensive operation, because the tail has to move. A final precision point: the bound is defined by the comparison, not by the presence of an element. Change `>=` to `>` and you get a different, equally well-defined position. That single-character degree of freedom is what generates the whole boundary family.
- What does the search return when the target is larger than every element?It returns `n`, the array length. That is a legal one-past-the-end insertion position, not an error code — the value belongs after everything. Any caller that reads the element at the returned index must range-check first, because there is no element there. Treating `n` as a bug is how correct bounds get wrapped in broken code.
- How do you tell from the returned index whether the target was actually present?Test both halves: `i < n` and `a[i] == target`. The bound alone cannot tell you — it returns a position for present and absent keys alike, and the position for an absent key looks identical to the position of a first occurrence. Skipping the range test reads out of bounds when the target exceeds everything.
- Does an insertion point mean anything on an unsorted array?No. The whole result rests on the invariant that everything before the returned index is smaller and everything from it on is not. Without sorted order the halving step discards the wrong side, and the returned index is arbitrary rather than wrong in a detectable way — the search still terminates and still returns a number, which makes the bug quiet.
It is the difference between asking a librarian "do you have this book?" and asking "which shelf gap does it go in?" — the second question has an answer even when the book is missing.
saying these in an interview costs you the question
- Says the search returns -1 when the key is absent
- Treats the returned index as proof the target exists
- Forgets the result can equal the array length
- Reads the element at the returned index without a range check
- Claims an insertion point requires the key to be present