[Question]: Given a sorted array and an integer x, write a program to find the lower bound of x.(arr[i] >= x))
Example 1: Input Format: N = 4, arr[] = {1,2,2,3}, x = 2 Result: 1 Explanation: Index 1 is the smallest index such that arr[1] >= x. Example 2: Input Format: N = 5, arr[] = {3,5,8,15,19}, x = 9 Result: 3 Explanation: Index 3 is the smallest index such that arr[3] >= x.
// TC: O(log(N))
// SC: O(1)
func findLowerBound(_ 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 arrInputLowerBound = [3, 5, 8, 15, 19]
let targetElementLowerBound = 9
let indexLowerBoundOutput = findLowerBound(arrInputLowerBound, targetElementLowerBound)
print("The lower bound is the index:", indexLowerBoundOutput)// 3 hence [3,5,8,15] & (arr[i] >= x))