You are given a sorted (non-decreasing) array arr and a number target. Return the upper bound of target — the smallest index i such that arr[i] > target (strictly greater).
If every element of arr is less than or equal to target, there is no such index inside the array — return arr.length, one past the last position.
Put differently: every element at indices 0 … i-1 is at most target, and arr[i] (if it exists) is the first element that beats it. Duplicates of target do not count — the bound lands after the last copy.
target sits on the left, everything greater sits on the right. You want the first index of the right part — and remember, equal values belong to the left part.arr[mid] > target, record mid as a candidate and search left; otherwise search right. Initialise the answer to arr.length so the no-greater-element case works for free.arr[i] >= target (equal counts); upper bound is the first index with arr[i] > target (strictly greater). If target appears in the array, lower bound points at its first copy and upper bound points just past its last copy. If target is absent, the two are equal.target and keep the array sorted. When every element is at most target, that spot is one past the end — index arr.length.target fails arr[mid] > target and pushes the search right. The bound naturally lands after the last duplicate — no special casing needed.upperBound(target) - lowerBound(target) — two binary searches bracket the run of equal values, giving the count in O(log n) without ever scanning it.arr[mid] >= target. Ceil is the value at the lower bound index; floor is the last index with arr[i] <= target, which is upperBound(target) - 1.arr[mid] > target, record and search right instead of left.upperBound(x) - lowerBound(x) counts the occurrences of x in a sorted array in O(log n) — the two bounds bracket every run of equal keys, a trick that reappears in Count Occurrences and First and Last Position problems.std::upper_bound, Python has bisect.bisect_right, Go has sort.Search. Interviewers still expect you to hand-roll it — the off-by-one traps are the whole point.Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 9 Output: 3 arr[3] = 10 is the first element strictly greater than 9 — indices 0…2 hold 2, 3, 7, all smaller.
Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 11 Output: 6 The two 11s are equal to the target, not greater — the bound skips past both to arr[6] = 25.
Input: arr = [2, 3, 7, 10, 11, 11, 25], target = 100 Output: 7 No element is greater than 100, so the upper bound is the array length, 7.
- 1 <= arr.size <= 10^6 - 1 <= arr[i] <= 10^6 - 1 <= target <= 10^6 - arr is sorted in non-decreasing order
Upper bound looks tiny, but it is the sharpest tool in the sorted-array toolbox. Master this one boundary-finding pattern and a dozen problems — first/last occurrence, counting duplicates, insert positions — collapse into the same six lines of binary search.
In plain English: find where the array stops being <= target and starts being > target. Formally: return the smallest index i with arr[i] > target, or arr.length if no such index exists.
Worked example — arr = [2, 3, 7, 10, 11, 11, 25], target = 11
index: 0 1 2 3 4 5 6
value: 2 3 7 10 11 11 25
<= <= <= <= <= <= > <- first strictly greater
answer: 6
Both 11s equal the target, so neither counts — the bound lands just past the last one.
A candidate who nails the definition before coding avoids the single most common bug in this problem — the strict-vs-non-strict comparison.
“Is the bound strict — do elements equal to the target count as greater?”
No. Upper bound wants strictly greater, so the answer lands after every copy of the target. This one word is the entire difference from lower bound.
“Can the answer be a position that does not exist in the array?”
Yes — if every element is at most the target, the answer is arr.length, one past the end. It is an insert position, not necessarily a readable index.
“Is the array sorted, and can it contain duplicates?”
Sorted non-decreasing, duplicates allowed — the algorithm must skip past an entire run of equal values in one logical step.
“Is the target guaranteed to be present in the array?”
No. The bound is well-defined for any value, present or not — that is what makes it more useful than plain search.
“How large can the array be?”
Up to a million elements. A single linear scan squeaks by, but this primitive is usually called many times, so the expected answer is the O(log n) binary search.
Before I code, let me pin down the definition: I need the smallest index whose element is strictly greater than the target — equal values do not count.
If every element is at most the target, I should return the array length itself, since the bound sits past the end.
The array is sorted, so I will binary search for that boundary in logarithmic time instead of scanning.
Because arr is sorted, every element satisfying arr[i] <= target forms a prefix, and every element satisfying arr[i] > target forms a suffix. There is exactly one boundary between them — the answer is the first index of the suffix.
[ <= <= <= <= | > > > ]
^
upper boundProbe the middle. If arr[mid] > target, then mid is a candidate answer and nothing to its right can be smaller — record it and search left. If arr[mid] <= target, then indices 0 … mid are all in the prefix — the boundary is strictly to the right. Either way the range halves.
Start with ans = arr.length. If the loop never finds an element greater than target, that default is already the correct answer — the everyone-is-smaller case costs zero extra code.
| Linear scan | Binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
Full code for both approaches lives in the Approaches selector below.
Key takeaway
Upper bound is boundary binary search: find the leftmost index where a monotone condition (arr[i] > target) flips to true, defaulting to n when it never does. Swap the condition to arr[i] >= target and the identical skeleton computes lower bound — one pattern, an entire family of problems.
ans = n
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if arr[mid] > target: ans = mid; hi = mid - 1
else: lo = mid + 1
return ans