[Question]: Upper Bound || Given a sorted array of N integers and an integer x, write a program to find the upper bound of x.
Example 1:
Input Format: N = 4, arr[] = {1,2,2,3}, x = 2
Result: 3
Explanation: Index 3 is the smallest index such that arr[3] > x.
Example 2:
Input Format: N = 6, arr[] = {3,5,8,9,15,19}, x = 9
Result: 4
Explanation: Index 4 is the smallest index such that arr[4] > x.
// TC: O(log(N))
// SC: O(1)
func findUpperBound(_ arr: [Int], _ targetElement: Int) -> Int {
let arrayCount = arr.count
var low = 0
var high = arrayCount - 1
var ans = arrayCount
while low <= high {
let mid = (low + high) / 2
// maybe an answer
if arr[mid] > targetElement {
ans = mid
// look for smaller index on the left
high = mid - 1
} else {
low = mid + 1 // look on the right
}
}
return ans
}
var arrInputUpperBound = [3, 5, 8, 9, 15, 19]
let targetElementUpperBound = 9
let indexUpperBoundOutput = findUpperBound(arrInputUpperBound, targetElementUpperBound)
print("The Upper bound is the index:", indexUpperBoundOutput)// 4 hence [15,19]