To find the upper bound of a number x
in a sorted array, we use a technique called Binary Search. This approach is much faster than checking each element because it divides the search range in half each time.
What is the Upper Bound?
The upper bound is the position (index) of the first element that is strictly greater than the given number x
. If no such element exists, it means all elements are less than or equal to x
, and we return the size of the array.
How It Works (Beginner Friendly)
We begin the search with two pointers:
low
pointing to the start of the array
high
pointing to the end
We also initialize a variable ans
to the length of the array. This will store the index of the potential upper bound if found.
We run a loop while low ≤ high
. At each step:
- We calculate the middle index
mid
- If the element at
mid
is greater than x
, this is a valid candidate for upper bound, so we:
- Update
ans = mid
- Move the
high
pointer to the left (mid - 1
) to see if there's an even smaller valid index
- If the element is less than or equal to
x
, then we move low
to the right (mid + 1
) because we’re looking for a greater number
After the loop, ans
will hold the index of the smallest number greater than x
. If no such element exists, it stays as arr.length
.
Why This Works
Since the array is sorted, binary search ensures we skip unnecessary elements and reduce the time complexity to O(log n). This makes the solution efficient even for very large arrays.