7.3 Upper Bound Searches
Lower bound finds the first position whose value is greater than or equal to a target.
7.3 Upper Bound Searches
Lower bound finds the first position whose value is greater than or equal to a target. Upper bound solves the complementary problem: it finds the first position whose value is strictly greater than the target.
At first glance, the distinction appears minor. In practice, upper bound is one of the most useful operations in ordered data structures because it identifies the position immediately after a group of equal values. Combined with lower bound, it enables efficient frequency counting, range queries, duplicate detection, interval processing, and index-based analytics.
Many database engines internally perform variations of lower-bound and upper-bound searches when locating records in sorted indexes. Understanding the difference between these operations helps explain how range scans, prefix searches, and ordered retrieval systems work.
Problem
Given a sorted sequence and a target value, find the first element strictly greater than the target.
Consider:
Index: 0 1 2 3 4 5
Value: 2 4 4 4 7 9
For target 4, the answer is index 4.
For target 7, the answer is index 5.
For target 9, the answer is index 6.
The returned position may point beyond the end of the array.
Solution
Use the same binary search framework as lower bound, but change the predicate.
Instead of:
nums[i] >= target
use:
nums[i] > target
Implementation:
func UpperBound(nums []int, target int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] > target {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
Example:
nums := []int{2, 4, 4, 4, 7, 9}
fmt.Println(UpperBound(nums, 4))
fmt.Println(UpperBound(nums, 7))
fmt.Println(UpperBound(nums, 9))
Output:
4
5
6
Understanding the Boundary
Suppose:
nums = [2, 4, 4, 4, 7, 9]
target = 4
Evaluate:
nums[i] > 4
Result:
Index: 0 1 2 3 4 5
Condition: F F F F T T
Binary search locates the first true value.
Notice how similar this looks to the lower-bound problem. The only difference is the predicate.
This observation reveals an important principle:
Binary search algorithms are usually predicate searches. The array merely provides a convenient way to evaluate the predicate.
Comparing Lower Bound and Upper Bound
Using the same data:
[2, 4, 4, 4, 7, 9]
Target:
4
Lower bound:
First element >= 4
Result:
1
Upper bound:
First element > 4
Result:
4
Visualizing the boundaries:
lower
|
v
[2, 4, 4, 4, 7, 9]
^
|
upper
The interval:
[lower, upper)
contains every occurrence of the target value.
This property makes upper bound extremely valuable.
Counting Duplicates
Suppose a search engine stores sorted identifiers:
[10, 10, 10, 15, 15, 20, 20, 20, 20]
How many times does 20 occur?
Compute:
count :=
UpperBound(nums, 20) -
LowerBound(nums, 20)
Results:
LowerBound = 5
UpperBound = 9
Count = 4
No scanning is required.
The count is determined in logarithmic time.
This pattern appears frequently in analytics systems, inverted indexes, columnar databases, and statistical processing.
Finding the Last Occurrence
Lower bound finds the first occurrence.
Upper bound can be used to find the last occurrence.
func LastOccurrence(nums []int, target int) int {
pos := UpperBound(nums, target)
if pos == 0 {
return -1
}
pos--
if nums[pos] == target {
return pos
}
return -1
}
Example:
[2, 4, 4, 4, 7, 9]
Upper bound of 4:
4
Subtract one:
3
Index 3 contains the last occurrence.
Range Queries
Upper bound becomes particularly useful when searching within intervals.
Suppose you need all values between:
100 and 200
inclusive.
Compute:
left := LowerBound(nums, 100)
right := UpperBound(nums, 200)
Every matching value lies within:
[left, right)
No individual element needs to be examined during the search phase.
This technique is heavily used in database indexes and time-series storage systems.
Prefix Searches
Strings can also be searched with upper bounds.
Consider:
apple
application
apply
banana
car
Suppose you want all strings beginning with:
app
A common technique is:
LowerBound("app")
UpperBound("app_max")
where the upper value sorts immediately after all strings beginning with the prefix.
The resulting interval contains every matching record.
Modern search systems often use variations of this strategy.
Upper Bound as a Generic Predicate Search
The true operation remains boundary detection.
A generic implementation looks identical to previous templates.
func FirstTrue(
lo, hi int,
ok func(int) bool,
) int {
for lo < hi {
mid := lo + (hi-lo)/2
if ok(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
Upper bound becomes:
result := FirstTrue(
0,
len(nums),
func(i int) bool {
return nums[i] > target
},
)
The search logic remains unchanged.
Only the predicate differs.
Database Perspective
Consider a B-tree index storing:
100
105
110
110
110
115
120
A query asks:
WHERE score > 110
The storage engine can perform an upper-bound search for 110.
The search immediately positions the scan at:
115
Every subsequent value automatically satisfies the condition.
This approach avoids examining records that cannot contribute to the result.
Many index operations are fundamentally lower-bound or upper-bound searches executed on tree structures rather than arrays.
Complexity Analysis
The search space is halved at every iteration.
For n elements:
| Operation | Complexity |
|---|---|
| Upper bound | O(log n) |
| Memory | O(1) |
The performance characteristics are identical to lower bound.
The only difference lies in the predicate.
Common Mistakes
Many implementations accidentally use:
nums[mid] >= target
inside an upper-bound search.
That condition produces a lower bound rather than an upper bound.
Another common mistake occurs when finding the last occurrence. The expression:
UpperBound(target) - 1
must be validated before indexing the array. If the target does not exist, the resulting position may refer to a different value.
A third mistake is confusing:
>= target
with:
> target
The distinction seems minor, but it completely changes the boundary being searched.
Takeaway
Upper bound finds the first position whose value is strictly greater than the target. Together, lower bound and upper bound define the complete range occupied by a value in a sorted collection. This pair of operations forms the foundation for duplicate counting, range searching, interval processing, prefix matching, database indexing, and many advanced ordered-data algorithms. Once you understand lower bound and upper bound as complementary boundary searches, a large class of search problems becomes a matter of selecting the correct predicate and locating the transition point.