Lower and upper bounds
Two first-true searches answer every question about a value in a sorted array with repeats: its first copy, its last copy, how many there are, where it goes.
Two tests, two boundaries
With repeated values "the index of 4" is ambiguous. Two precise questions replace it, and each is a first-true search from the first module with a different test.
-
Step 1 / 2
Lower bound of 4: the first index with a[i] ≥ 4. Here 1, the first copy of 4.
-
Step 2 / 2
Upper bound of 4: the first index with a[i] > 4. Here 4, one past the last copy.
Both tests switch once because the array is sorted. Both searches return a value between 0 and n, and n is a legitimate answer: it means every element fails the test.
The lower bound, step by step
Each step either keeps mid (it passes, so it may be the first) or discards it with everything to its left.
The lower bound of 4 in an array with three copies of it.
-
Step 1 / 6lo0hi8
We want the first index with a[i] ≥ 4. The answer is in [lo, hi) = [0, 8); hi = 8 stands for "nothing passes".
-
Step 2 / 6lo0mid4hi8
a[4] = 7: 7 ≥ 4. It passes, so the first pass is at 4 or earlier: hi = 4.
-
Step 3 / 6lo0mid2hi4
a[2] = 4: 4 ≥ 4. It passes, so the first pass is at 2 or earlier: hi = 2.
-
Step 4 / 6lo0mid1hi2
a[1] = 4: 4 ≥ 4. It passes, so the first pass is at 1 or earlier: hi = 1.
-
Step 5 / 6lo0mid0hi1
a[0] = 2: 2 < 4. It fails, and so does everything before it: lo = 1.
-
Step 6 / 6answer1
lo = hi = 1. Index 1 is the first index with a[i] ≥ 4.
known to failknown to passbeing tested
What the two bounds answer
Almost every question about a value in a sorted array is one bound, the other, or their difference.
| Question | Answer | In the example, x = 4 |
|---|---|---|
| Is x present? | lower(x) < n and a[lower(x)] = x | a[1] = 4: yes |
| First index of x | lower(x), if present | 1 |
| Last index of x | upper(x) − 1, if present | 3 |
| How many copies of x | upper(x) − lower(x) | 4 − 1 = 3 |
| Where to insert x and keep order | lower(x) (before equal values) or upper(x) (after them) | 1 or 4 |
| How many values lie in [L, R] | upper(R) − lower(L) | for [4, 9]: 7 − 1 = 6 |
| How many values are at least x | n − lower(x) | 8 − 1 = 7 |
Write one function, firstTrue(lo, hi, test), and call it with different tests. Two near-identical loops are where the off-by-one errors creep in.
The code
The insertion point is the lower bound of a value that may or may not be present, so the reference solution
to Where a value belongs is the lower bound itself. Change < to ≤ in the test
and it becomes the upper bound.
def search_insert(nums, target):
lo, hi = 0, len(nums) # the answer is in [lo, hi); hi = n means "after everything"
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] >= target:
hi = mid # mid passes: the first pass is mid or earlier
else:
lo = mid + 1 # mid fails, and so does everything before it
return lo#include <vector>
int solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size(); // the answer is in [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo; // same as std::lower_bound(...) - nums.begin()
}class Solution {
public int searchInsert(int[] nums, int target) {
int lo = 0, hi = nums.length; // the answer is in [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo;
}
}function searchInsert(nums, target) {
let lo = 0, hi = nums.length; // the answer is in [lo, hi)
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo;
}fn solve(nums: &[i64], target: i64) -> i64 {
let (mut lo, mut hi) = (0usize, nums.len()); // the answer is in [lo, hi)
while lo < hi {
let mid = lo + (hi - lo) / 2;
if nums[mid] >= target { hi = mid } else { lo = mid + 1 }
}
lo as i64 // the library call: nums.partition_point(|&x| x < target)
}import Data.Array
solve :: [Int] -> Int -> Int
solve nums target = go 0 n
where
n = length nums
a = listArray (0, n - 1) nums
-- the answer is in [lo, hi)
go lo hi
| lo >= hi = lo
| a ! mid >= target = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2The same code is the reference solution to Where a value belongs in a sorted array, where it is compiled and run against the tests in all six languages.
A bound with a different test
The test does not have to compare against a fixed value. In Research impact from sorted citation
counts, paper i together with every paper after it has at least c[i] citations each, and there
are n − i of them. The h-index is the largest h with h papers of h citations, which turns into
a first-true search:
h-index from sorted citations
hIndex(c)
- Test at index i: c[i] ≥ n − i. As i grows, c[i] does not fall and n − i falls, so once true it stays true.
- Find the first index i that passes, with the lower-bound loop over [0, n].
- Return n − i. If nothing passes, i = n and the h-index is 0.
In Count the partners that clear a threshold, sort the potions once, then for each spell s the potions that work are those from the first p with s × p ≥ success onwards: one lower bound per spell. The product needs 64-bit arithmetic.
Many queries on one array: sort once in O(n log n), then answer each query with one or two bounds.
Library calls
| Language | Lower bound | Upper bound |
|---|---|---|
| Python | bisect.bisect_left(a, x) | bisect.bisect_right(a, x) |
| C++ | std::lower_bound(first, last, x) | std::upper_bound(first, last, x); std::equal_range gives both |
| Rust | a.partition_point(|&v| v < x) | a.partition_point(|&v| v <= x) |
| Java | no array version; write the loop | TreeSet.ceiling and higher give values, not indices |
| JavaScript | none; write the loop | none |
| Haskell | none for arrays; Data.Set.lookupGE gives the value | Data.Set.lookupGT |
Rust's partition_point is the most honest name of the lot: it takes the test and returns the first index where the test stops holding. That is all a bound is.