Implement Upper Bound

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 → index 4 (value 6), because indices 0–3 are ≤ 4 and index 4 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

1. Search Window – Maintain two pointers, low and high, around the current candidate range.
2. Potential Answer Tracker – Keep ub, the best upper-bound index seen so far, initialised to n (meaning “not found yet”).
3. Binary Search Loop
   • Compute mid.
   • If arr[mid] > x, mid is a valid upper bound. Save it in ub and continue searching left (smaller indices) for an even earlier position.
   • Otherwise (arr[mid] ≤ x) move low right to discard non-qualifying elements.
4. When the loop terminates, ub holds either the first index of an element > x or n 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)

Code 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.
• Loop ends when low crosses high; at that point every potential position is checked and ub is final.

Dry Run (arr = [1, 2, 4, 4, 6], x = 4)

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.