The challenge
Return the first index i with nums[i] > target, or n if no value qualifies.
Ascending order; duplicates allowed. Empty input returns 0.
Example
[1, 2, 2, 2, 5, 8], target = 2 → 4.
Use the walkthrough below to inspect the input and each state change.
See Upper bound, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indicestarget = 2
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 5
Step 01 / 6
Find the first value > target
Reset the inclusive candidate interval. The returned boundary is allowed to equal the array length.
left = 0; right = 5Recorded result so far
Not resolved
View exact input
Input: [1,2,2,2,5,8] · target = 2
Put it into code
Use a strict predicate. Equal values belong on the discarded left side, so the search moves beyond the entire duplicate run.
Indices are zero-based. C++ uses C++17 or later.
def upper_bound(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return left # len(nums) if no value qualifies.#include <vector>
int upper_bound(const std::vector<int>& nums, int target) {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1;
else right = mid - 1;
}
return left; // nums.size() if no value qualifies.
}