Find Lower bound of x

[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))

Leave a Comment

Your email address will not be published. Required fields are marked *