Back to Study Material Data Structures and Algorithms

Lower Bound and Upper Bound

Lower bound and upper bound are two specific variants of binary search that locate the boundary positions of a target value in a sorted array, even when du...

Lower Bound and Upper Bound

Defining the Bounds

Lower bound and upper bound are two specific variants of binary search that locate the boundary positions of a target value in a sorted array, even when duplicates are present. Understanding these operations precisely is essential because they appear constantly in competitive programming, database index design, and interval queries.

The lower bound of a target value x in a sorted array is the index of the first element that is greater than or equal to x. If every element is less than x, the lower bound is one past the last index, equal to the array length. The lower bound tells you where x would be inserted to keep the array sorted, or where the first occurrence of x lives if x is present.

The upper bound of x is the index of the first element that is strictly greater than x. If no element exceeds x, the upper bound is also one past the last index. The range from the lower bound to the upper bound (exclusive) contains exactly all occurrences of x in the array.

A worked example: in the sorted array 1, 2, 4, 4, 4, 7, 9, 11, the lower bound of 4 is index 2 and the upper bound of 4 is index 5. The slice from index 2 to index 5 contains three 4s. The count of occurrences equals upper bound minus lower bound, which is 5 minus 2 equals 3.

Time complexity for both operations is O(log n). Space complexity is O(1) for iterative implementations.

The standard library provides these directly. In C++, std::lower_bound and std::upper_bound implement these operations on sorted ranges. In Java, Arrays.binarySearch returns a negative insertion-point encoding that can be decoded to recover the lower bound. In Python, the bisect module provides bisect_left for lower bound and bisect_right for upper bound.

Interview tip: practice implementing lower bound and upper bound from scratch. The off-by-one errors in the loop termination condition and the answer extraction are the most common bugs, and writing them cleanly under pressure demonstrates careful programming habits.

Implementing Lower Bound Correctly

Implementing lower bound without bugs requires careful attention to loop invariants. The invariant to maintain is that the answer always lies in the half-open interval from low to high. When the loop terminates with low equal to high, that value is the answer.

Pseudocode for lower bound: set low to 0 and high to n. While low is less than high, compute mid as low plus (high minus low) divided by 2. If the array at mid is less than the target, set low to mid plus 1. Otherwise set high to mid. Return low.

Notice that high starts at n rather than n minus 1. This handles the case where the target is larger than every element, in which case the lower bound should be n, one past the end. Notice also that when the array at mid is less than the target, low moves up to mid plus 1, skipping mid definitively. When the array at mid is greater than or equal to the target, high moves down to mid, not mid minus 1, because mid itself might be the answer.

Pseudocode for upper bound: set low to 0 and high to n. While low is less than high, compute mid as low plus (high minus low) divided by 2. If the array at mid is less than or equal to the target, set low to mid plus 1. Otherwise set high to mid. Return low.

The only difference is changing the comparison from strictly less than to less than or equal to. This ensures that equal elements push the left pointer past mid, landing the answer at the first position strictly after all equal elements.

A worked example: in the array 3, 3, 3, 3, 3 searching for 3, the lower bound returns 0 and the upper bound returns 5. These are the correct answers because all five positions hold 3.

Interview tip: trace through your implementation on an array of all equal elements before declaring it correct. This edge case catches most off-by-one errors in both lower and upper bound implementations.

Applications in Range Queries and Problems

The lower bound and upper bound operations unlock a wide range of efficient algorithms that would otherwise require O(n) time per query. By reducing range membership queries to two binary searches, they transform O(n) problems into O(log n) problems.

Counting occurrences: as shown earlier, the number of times x appears in a sorted array equals upper_bound(x) minus lower_bound(x), computed in O(log n).

Finding the nearest element: the element nearest to x in a sorted array is either the element at the lower bound or the one just before it. Check both positions and return the closer one. This runs in O(log n) compared to O(n) for a linear scan.

Range counting: to count elements in a sorted array that fall between L and R inclusive, compute lower_bound(L) and upper_bound(R). The answer is upper_bound(R) minus lower_bound(L). This is O(log n) per query.

Inserting into sorted order: lower_bound gives the correct insertion position to maintain sorted order, which is exactly what insertion sort uses in its binary insertion sort variant. This reduces the number of comparisons in insertion sort from O(n squared) to O(n log n), though the number of swaps remains O(n squared).

A worked example from a real interview problem: given a sorted array of timestamps and a time window, count how many events fall within each query window efficiently. For each query (start, end), compute lower_bound(start) and upper_bound(end) and subtract. With q queries and an array of n events, this runs in O((n plus q) log n) rather than O(n times q).

Time complexity per operation: O(log n). Space complexity: O(1).

Interview tip: when you see the phrase count elements satisfying a condition in a sorted structure, immediately think of combining lower bound and upper bound. This pattern appears in sliding window problems, event scheduling, and histogram queries.