Lower and upper bound
mediumPlain binary search finds *an* occurrence and cannot tell you how many there are. lowerBound and upperBound can - and their difference is the count, in O(log n).
O(log n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How lower and upper bound works
Plain binary search answers 'is 14 here?' with some index holding 14 - and with four copies present, which one you get is an accident of the halving. It cannot say how many there are, or where a new 14 should be inserted. Reframing fixes that: stop searching for a value and start searching for a boundary.
lowerBound returns the first index with a[i] >= x, upperBound the first with a[i] > x. The machinery is a half-open range [lo, hi): hi starts at n, the loop runs while lo < hi, and the branch is hi = mid when a[mid] is big enough - mid stays a candidate - versus lo = mid + 1 when it is too small. When the pointers meet they name the boundary. Returning n means 'past the end', and no -1 case exists.
This one shape is Python's bisect_left and bisect_right, C++'s std::lower_bound and std::upper_bound, and the idea behind Java's floorKey and ceilingKey. upperBound(x) - lowerBound(x) counts the occurrences of x in O(log n), and lowerBound alone is the insert position that keeps a sorted array sorted.
Step by step
- Run lowerBound(14) on [2, 5, 5, 5, 8, 8, 11, 14, 14, 14, 14, 19, 23, 23, 27]: lo = 0, hi = 15.
- mid = 7 and a[7] = 14. Not less than 14, so index 7 might itself be the answer - hi = 7 keeps it in range.
- mid = 3, a[3] = 5 < 14: everything through index 3 is too small - lo jumps to 4.
- mid = 5 gives 8, then mid = 6 gives 11 - both below 14, so lo climbs to 6, then 7.
- lo meets hi at 7. The first 14 sits at index 7 - found in 4 probes without ever scanning the duplicates.
- Run it again as upperBound - the comparison becomes a[mid] <= 14 - and it returns 11. 11 - 7 = 4 copies of 14, counted in O(log n).
Complexity
| Worst case time | O(log n) |
|---|---|
| Space | O(1) |
Same halving, with a half-open range so 'past the end' needs no special case.
Reference implementation
Python
def lower_bound(a, x):
"""First index i with a[i] >= x. len(a) if none."""
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(a, x):
"""First index i with a[i] > x."""
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] <= x:
lo = mid + 1
else:
hi = mid
return lo
# count of x == upper_bound(a, x) - lower_bound(a, x)JavaScript
function lowerBound(a, x) { // first i with a[i] >= x
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
}
function upperBound(a, x) { // first i with a[i] > x
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}Worth noticing
The half-open range is what makes this clean
hi starts at n, not n-1, and the loop is `lo < hi`. That lets the answer be 'past the end' without a special case, and it is why `hi = mid` rather than `mid - 1` - mid is still a candidate.
Counting occurrences for free
upperBound(x) − lowerBound(x) is exactly how many copies of x the array holds, in O(log n). Plain binary search finds *an* occurrence and cannot tell you that.
This is `bisect_left` and `bisect_right`
Python's bisect, C++'s std::lower_bound, Java's floorKey/ceilingKey - all the same routine. Learning this shape once covers 'insert position', 'first element ≥ x' and 'range query' problems.
Common pitfalls
- Writing hi = mid - 1 in the half-open version. When a[mid] >= x, mid is still a viable answer - discard it and the loop converges below the true boundary.
- Confusing the two bounds: a[mid] < x gives lowerBound, a[mid] <= x gives upperBound. Pick the wrong one and counts and insert positions silently shift by the number of duplicates.
- Forgetting the return value can be n. Indexing a[lowerBound(a, x)] without a bounds check reads past the end whenever x exceeds every element.
- Pairing hi = n with while lo <= hi. The half-open range needs lo < hi - the inclusive condition eventually probes a[n] or spins forever on hi = mid.
- Testing presence wrong: lowerBound tells you where x would be, not that it is there - you still need result < n and a[result] == x.
Where it is used
- Counting elements in a range: two bounds on a sorted timestamp array give 'events between t1 and t2' in O(log n).
- Keeping a list sorted under inserts - Python's bisect.insort finds the slot with exactly this routine.
- The O(n log n) longest increasing subsequence: each element replaces the first tail that is >= it, located by lowerBound.
- C++ equal_range, std::map lower_bound, Java TreeMap ceilingKey - every ordered container ships this pair.
Frequently asked questions
What is the time and space complexity of lower bound and upper bound?
Worst case O(log n) time - the same halving as binary search, with the half-open range meaning duplicates cost nothing extra - and O(1) space. Counting occurrences via upperBound minus lowerBound is two searches, still O(log n) total.
What is the difference between lower bound and upper bound?
lowerBound(x) is the first index whose value is greater than or equal to x; upperBound(x) is the first index whose value is strictly greater. On [5, 7, 7, 9] the bounds for 7 are 1 and 3. In code they differ by one character: < versus <= in the comparison.
How do I count how many times a value appears in a sorted array?
upperBound(x) - lowerBound(x). The two boundaries bracket the run of equal values exactly, so the difference is the count - 0 when absent - in O(log n), without scanning a single duplicate. C++ packages the pair as std::equal_range; in Python it is bisect_right minus bisect_left.
Is lower bound the same as bisect_left in Python?
Yes. bisect_left returns the first position where x could be inserted while keeping order - exactly lowerBound - and bisect_right matches upperBound. C++'s std::lower_bound and std::upper_bound return iterators to the same positions. Same loop, same half-open convention, different standard-library names.