Lower Bound, Upper Bound and the Insertion Point

When a sorted array holds repeated values, one target can sit at several indices, and the useful answers are where that run starts and where it ends. The lower bound of a target is the first index whose value is at least the target; the upper bound is the first index whose value is greater than it. This card covers both, the variant of binary search that finds them, and the count and insertion point they give. You meet them when counting the records that share a key, selecting everything in a range of values, and inserting into a sorted list.

Both come from one change to the search. The range becomes half-open, written [low, high): low is the first index still in play and high is one past the last, so high starts at the array's length and the loop runs while low < high. When the middle value is smaller than the target, the answer lies to its right, so low = mid + 1. Otherwise the middle value may itself be the answer, so high = mid keeps it in play, which works because high is excluded from the range. When the loop ends, low equals high and is the lower bound. Changing "smaller than" to "smaller than or equal to" gives the upper bound.

The table gives both bounds for five targets, from a run of that search on the same array. Read the rows for 4 and 8, which are not in the array.

The count of a value is the upper bound minus the lower bound, and it is 0 exactly when the two are equal; then both are the insertion point, the index where the value would go to keep the array sorted. For 8, larger than everything, both bounds are 6, the array's length: one past the end, where an append would put it.

The upper bound is not the last occurrence. For 3 the last occurrence is index 3, one less than the upper bound, and it exists only when the count is above 0. Reading the upper bound as the last occurrence reads one item too far, and past the end of the array when the target is the largest value. An exact search does not answer these questions either: on a run of 3s it stops at whichever 3 a middle index lands on first.

The two bounds turn binary search from a yes-or-no lookup into a tool for ranges: the values from a to b occupy the indices from the lower bound of a up to, but not including, the upper bound of b.