Find the Upper Bound of a Target in a Sorted Array
Solve this Problem
Given an array
nums sorted in non-decreasing order (duplicates allowed) and an integer target, return its upper bound — the index of the first element that is strictly greater than target. If no element is greater, return nums.length.
Together, lower bound and upper bound let you find every occurrence of a value in a sorted array in O(log n): upperBound - lowerBound is exactly the count.
Test Case 1:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 5
Output:5
Explanation:Index 5 (value 7) is the first position whose value is strictly greater than 5.
Test Case 2:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 4
Output:2
Explanation:The first value strictly greater than 4 is at index 2.
Test Case 3:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 9
Output:7
Explanation:Nothing is strictly greater than 9, so the bound sits one past the last index.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁴ - ◆
-10⁴ ≤ nums[i], target ≤ 10⁴ - ◆
nums is sorted in non-decreasing order (duplicates are allowed)
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int upperBound(int[] nums, int target) { |
| 3 | int lo = 0, hi = nums.length - 1, ans = nums.length; |
| 4 | while (lo <= hi) { |
| 5 | int mid = lo + (hi - lo) / 2; |
| 6 | if (nums[mid] > target) { |
| 7 | ans = mid; |
| 8 | hi = mid - 1; |
| 9 | } else { |
| 10 | lo = mid + 1; |
| 11 | } |
| 12 | } |
| 13 | return ans; |
| 14 | } |
| 15 | } |
| 16 |
1
3
5
5
5
7
9
0
1
2
3
4
5
6
↑lo
↑hi
Variables
lo
0hi
6ans
7INITIALIZE
Search [0, 6] for the leftmost index where nums[i] > 5. Default ans to 7 (past the end) until something qualifies.
Step 1 / 5
Approach & Solutions
Brute Force — Linear Scan
BruteWalk left to right and return the first index whose value is strictly greater than target. Correct on any array, but it never uses the sortedness that lets binary search skip most of the comparisons.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int upperBound(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 if (nums[i] > target) return i;
5 }
6 return nums.length;
7 }
8}Optimal — Binary Search
OptimalThe upper bound is the leftmost index whose value is strictly greater than target — the same shape as lower bound, just with a strict comparison. Whenever nums[mid] > target, mid is a valid candidate — record it and keep searching left for an even earlier one. Otherwise the answer must be further right.
Time
O(log n)Space
O(1)Java
1class Solution {
2 public int upperBound(int[] nums, int target) {
3 int lo = 0, hi = nums.length - 1, ans = nums.length;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 if (nums[mid] > target) {
7 ans = mid;
8 hi = mid - 1;
9 } else {
10 lo = mid + 1;
11 }
12 }
13 return ans;
14 }
15}