Upper Bound
Scenario
You are processing time-series data and need to count exactly how many transactions occurred at exactly `12:00:00`.
If there are a million transactions that second, how do you count them in O(log N) time without iterating through them?
Why it exists
Problem: Lower Bound finds the start of a sequence of duplicates. But to process a range or count the frequency of an element, you also need to know where the sequence ends.
Naive approach: Use Lower Bound to find the start, then linearly scan forward until the value changes. This degrades to O(N) time for large blocks of duplicates.
Better idea: Use Upper Bound to find the exact exclusive limit (the first element STRICTLY GREATER than the target) in O(log N) time. Subtracting the Lower Bound index from the Upper Bound index gives the exact frequency instantly.
Mental model
If Lower Bound finds the front door of a building, Upper Bound finds the back door—specifically, the first step outside the back door.
Upper Bound returns the index of the first element that is STRICTLY GREATER THAN the target. Even if the current element matches the target, the algorithm treats it as 'too small' (or 'not great enough') and pushes the `low` pointer rightward (`low = mid + 1`). It only updates the potential answer when it finds an element definitively larger than the target.
Repeated decision: Is `arr[mid] > target`? If yes, the boundary is at `mid` or to its left (`high = mid`). If no (meaning it is `<= target`), the boundary is strictly to the right (`low = mid + 1`).
Explanation
The only difference between Lower Bound and Upper Bound is the relational operator in the predicate.
- Lower Bound predicate: `element < target` (Finds first element `>= target`)
- Upper Bound predicate: `target < element` (Finds first element `> target`)
If the target value does not exist in the array at all, both Lower Bound and Upper Bound will return the exact same index (the insertion point).
In computer science, combining these two algorithms creates a 'Half-Open Interval': `[start, end)`. Half-open intervals are the standard for loop boundaries because they prevent off-by-one errors. You can loop over all duplicates safely using `for (int i = lower; i < upper; i++)`. Because `upper` points one index *past* the target, the loop terminates exactly when it should.
Key points
- Strictly Greater: Upper Bound finds the first element > target, marking the end of a sequence.
- Frequency Counting: Frequency = (Upper Bound Index) - (Lower Bound Index). Calculates count in O(log N) time.
- Half-Open Intervals: Provides the exclusive `end` index for safe `[start, end)` iteration.
Pattern: Rightmost Boundary / Exclusive Limit
Recognition cues:
- The problem asks for the 'last occurrence' of an element (Upper Bound - 1).
- You need to count the frequency of elements in a sorted array.
- The problem asks for the first element strictly greater than X.
Failure signals
- You used `>=` instead of `>` in your Upper Bound logic, accidentally implementing Lower Bound instead.
Engineering examples
Time-Series Data Aggregation
Counting occurrences or isolating a time window `[start_time, end_time]` in logs.
Lower Bound gets the start, Upper Bound gets the end. The exact slice is isolated in O(log N) without scanning.
When not to use
- You need the element itself: Upper Bound returns the element *after* the target. If you just need to check if an element exists, standard Binary Search is sufficient.
Common mistakes
- Confusing the condition with Lower Bound: If you use `arr[mid] >= target`, you are writing Lower Bound. Upper Bound MUST be strictly `arr[mid] > target`.
- Returning Upper Bound for 'Last Occurrence': Upper Bound gives the index *after* the last occurrence. If asked for the last occurrence of a target, you must return `upper_bound_index - 1` (and handle out-of-bounds checks).
Glossary
- relational operator
- A mathematical symbol used to compare two values, like <, >, or ==.
- Half-Open Interval
- A range that includes the starting point but stops just before the ending point.
- off-by-one errors
- A very common bug where a loop runs exactly one time too many or one time too few.
Recall questions
- What is the predicate condition difference between Lower Bound and Upper Bound?
- How do you calculate the frequency of an element using these algorithms?
- If an element does not exist in the array, what is the relationship between its Lower Bound and Upper Bound?
Questions & answers
Find the first and last position of an element in a sorted array.
Use Lower Bound to find the first position. Use Upper Bound to find the exclusive end. The last position is `UpperBound - 1`. If Lower == Upper, the element isn't in the array.
Approach: Half-Open Interval construction.
Implement the upper bound algorithm.
Set `ans = len`. While `low <= high`: if `arr[mid] > target`, update `ans = mid` and `high = mid - 1` (search left for an earlier valid limit). Else, `low = mid + 1` (search right).
Approach: Upper Bound with tracking variable.
Continue learning
Previous: Lower Bound
Next: Binary Search on the Answer
Related: Lower Bound
Related: Binary Search