How do lower bound and upper bound differ on a sorted array holding several copies of the target?
answer
- only the comparison changes between them
- one uses at-least, the other strictly-greater
- one lands on the first copy
- the other lands one past the last copy
- subtract the two indices to count
basics
~20 sLower bound returns the first index whose element is at least the target: the first copy. Upper bound returns the first strictly greater index: one past the last copy. Their difference is the occurrence count.
solid answer
~50 sBoth are the same search with one character changed. Lower bound finds the first index where `a[i] >= target`; upper bound finds the first index where `a[i] > target`. On an array holding several copies, lower bound lands on the first copy and upper bound lands one past the last copy — never *on* a copy — so `upper - lower` is exactly the number of occurrences, in 2·O(log n) comparisons with no scanning. The pair also brackets the equal run as a half-open slice `[lower, upper)`, which is the natural way to hand a range query its endpoints. When the target is absent, both searches stop at the same index — the shared insertion point — and the difference is 0, which is the correct count without any special case. The two bounds never cross.
go deeper
Memorise the two predicates and say which lands where: at-least gives the first copy, strictly-greater gives one past the last. Getting the direction right matters more than the terminology.
Explain that both are the same monotone-predicate search with one comparison swapped, and derive the occurrence count as a subtraction. Expect to be pushed on the absent-key case.
Show why the half-open convention removes the special cases, and why the two bounds beat find-then-scan on exactly the duplicate-heavy input that makes the query interesting in the first place.
Frame the bounds as the primitive that ranking, percentile and range-query features are built from, so choosing the tie-inclusive or tie-exclusive count becomes an explicit product decision rather than an accident.
## One template, one comparison The boundary family looks like several algorithms and is really one. Both bounds answer *first index where the predicate becomes true* over a sorted array; only the predicate differs. | Bound | Predicate | Lands on | | --- | --- | --- | | Lower bound | `a[i] >= target` | the first copy of the target, or the insertion point if absent | | Upper bound | `a[i] > target` | one past the last copy, or the same insertion point if absent | Because the array is sorted, each predicate is *monotone*: once true at some index it stays true for every later index. That monotonicity is the only reason halving is legal, and it is what both bounds share. ## A worked run A sorted score table: ``` index: 0 1 2 3 4 5 value: 4 7 7 7 11 15 ``` - Lower bound of 7 = **1**. Index 0 holds 4, which is below 7; index 1 is the first element not below 7. - Upper bound of 7 = **4**. Indices 1..3 hold 7, which is not *strictly* greater; index 4 holds 11, the first strictly greater element. - Occurrences of 7 = 4 − 1 = **3**. Correct, and no element was scanned. Note what the upper bound is *not*: it is not index 3, the last copy. Off-by-one here is the single most common error in the whole boundary family, and the phrasing that prevents it is **"one past the last copy"** — never "the last copy". ## Half-open slices, and why the convention pays The pair `[lower, upper)` is a half-open range: include the left endpoint, exclude the right. Half-open is not a stylistic taste — it is what makes the arithmetic work out with no adjustments: - The count is `upper − lower`, plain subtraction with no ±1. - An empty range is `lower == upper`, which is exactly what an absent key produces. - Ranges concatenate: the run of 7s ends where the run of 11s begins, no shared or skipped index. If instead you insisted on inclusive endpoints, the last copy is `upper − 1`, the count is `upper − lower` still but the endpoint is undefined when the count is zero, and every caller has to guard against it. The half-open convention makes the degenerate case *fall out* rather than needing a branch. ## The absent key is not a special case Search for 9 in the table above. Lower bound: the first element at least 9 is 11 at index 4. Upper bound: the first element strictly greater than 9 is also 11 at index 4. Both return 4, the difference is 0, and 0 is the honest count. The same holds for a value past the end: search for 20, and both bounds return 6, the array length, difference 0. This is worth stating out loud in an interview, because a candidate who says "the bounds always differ" has quietly assumed the target is present. The two bounds coincide *exactly when* the target is absent, and that equivalence is a useful presence test in its own right. ## Direction, and what each bound counts The two indices also read as counts, which is where they earn their keep in ranking and percentile work: - `lowerBound(x)` = the number of elements **strictly less than** x. - `upperBound(x)` = the number of elements **less than or equal to** x. Both counts are exact regardless of whether x is present. Choosing between them is therefore not a matter of taste: if ties should count against you, use the second; if ties should not, use the first. Reaching for the wrong one is a silent logic bug, not a crash — the number is plausible and wrong. ## Cost, and the alternative that fails Each bound is O(log n) comparisons, so counting occurrences with the pair is O(log n) overall. The tempting alternative — find any occurrence, then walk left and right to the ends of the equal run — is O(n) in the worst case, because the run can be the whole array. On a table of a million rows where one value dominates, the scan degrades to a full pass while the two bounds stay at roughly forty comparisons. The asymptotic gap here is not academic; it is the difference between a constant-time-feeling query and a linear one on the exact input distribution (heavily repeated keys) that motivated the query in the first place. A last precision note: subtraction of the two bounds counts occurrences *of one value*. Generalise the predicates and the same pair delimits any contiguous range — the elements in `[low, high)` are the slice from `lowerBound(low)` to `lowerBound(high)`, again with no adjustment terms.
- What is the difference between the two bounds when the target is absent?Zero. Both searches stop at the same index — the shared insertion point — because no element equals the target, so nothing separates "at least" from "strictly greater". That makes the count formula `upper - lower` correct with no special case, and it means coinciding bounds are themselves a presence test.
- How do you get the index of the last copy from these bounds?It is `upper - 1`, and it is only meaningful when `upper > lower` — that is, when at least one copy exists. Asking for the last copy of an absent key is asking for an element that is not there, which is precisely why the half-open convention prefers to expose `upper` and let callers subtract when they know the count is positive.
- Is counting occurrences this way still logarithmic?Yes. Two independent searches over the same array cost 2·O(log n) comparisons, which is still O(log n). The alternative of finding one occurrence and walking outward to the run's ends is O(n) in the worst case, since the equal run can span the entire array — the exact input the count query is usually asked about.
- Which bound tells you how many elements are strictly less than a value?The lower bound, directly. Everything before that index is strictly smaller by definition, so the index itself is the count. The upper bound is the count of elements less than or equal to the value. Both are exact whether or not the value appears, which is why they are the natural primitives for ranking and percentile work.
saying these in an interview costs you the question
- Says upper bound returns the index of the last copy
- Thinks counting copies needs a linear scan after the search
- Claims the two indices always differ, even for an absent key
- Believes upper bound points at an element equal to the target
- Confuses upper bound with the largest element below the target