In a sorted array arr[]
, the upper bound of x
is the index of the first element that is strictly greater than x
.
If every element in the array is ≤ x
, the conventional upper-bound position is n
(one past the last index).
Here’s the [Problem Link] to begin with.
Example
arr = [1, 2, 4, 4, 6], x = 4
Upper bound → index4
(value6
), because indices0–3
are ≤4
and index4
is the first> 4
.
Upper-bound queries power range searches, frequency counts, and insertion-point calculations. A tailored binary-search achieves this in logarithmic time.
Optimal Solution (Binary Search)
Intuition & Approach
- Search Window – Maintain two pointers,
low
andhigh
, around the current candidate range. - Potential Answer Tracker – Keep
ub
, the best upper-bound index seen so far, initialised ton
(meaning “not found yet”). - Binary Search Loop
- Compute
mid
. - If
arr[mid] > x
,mid
is a valid upper bound. Save it inub
and continue searching left (smaller indices) for an even earlier position. - Otherwise (
arr[mid] ≤ x
) movelow
right to discard non-qualifying elements.
- Compute
- When the loop terminates,
ub
holds either the first index of an element >x
orn
if such an element doesn’t exist.
Code Implementation
def upperBound(arr: [int], x: int, n: int) -> int:
n = len(arr) # total number of elements
ub = n # default upper bound (past-the-end)
low, high = 0, n - 1 # binary-search boundaries
while low <= high:
mid = (low + high) // 2 # midpoint of current window
if arr[mid] > x:
ub = mid # arr[mid] is a better (earlier) upper bound
high = mid - 1 # search the left half for an even smaller index
else: # arr[mid] <= x → discard left half including mid
low = mid + 1 # shift window right to find a greater element
return ub # final upper-bound index (or n if none)
PythonCode Explanation
ub
=n
acts as a sentinel meaning “no upper bound found yet.”- Case
arr[mid] > x
mid
itself qualifies. Store it and shrink the window leftward to see if an earlier qualifying index exists.
- Case
arr[mid] <= x
- All indices ≤
mid
are ≤x
, so the next valid upper bound must be to the right.
- All indices ≤
- Loop ends when
low
crosseshigh
; at that point every potential position is checked andub
is final.
Dry Run (arr = [1, 2, 4, 4, 6]
, x = 4
)
Step | low | high | mid | arr[mid] | ub update | Next Window |
---|---|---|---|---|---|---|
1 | 0 | 4 | 2 | 4 | — (still 5) | low = 3 |
2 | 3 | 4 | 3 | 4 | — (still 5) | low = 4 |
3 | 4 | 4 | 4 | 6 | ub = 4 | high = 3 |
End | — | — | — | — | ub = 4 | loop stops |
Result 4, matching the expected upper-bound index.
Time & Space Complexity
- Time:
O(log n)
— each iteration halves the search space. - Space:
O(1)
— only a few integer variables are used.
Conclusion
By slightly tweaking classic binary search, tracking the last “good” index, we can compute the upper bound in logarithmic time and constant space. This pattern generalises to numerous “first/last element with property P” queries on sorted data. Happy coding!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.