Find Ceil & Floor element in an array

[Question]: You’re given an sorted array arr of n integers and an integer x. Find the floor and ceiling of x
The floor of x is the largest element in the array which is smaller than or equal to x.
The ceiling of x is the smallest element in the array greater than or equal to x.
We will use Binary Search here

// TC: O(log(N))
// SC: O(1)
func findCeil(_ arr: [Int], _ targetElement: Int) -> Int {
    let arrayCount = arr.count
    var low = 0
    var high = arrayCount - 1
    var ans = arrayCount//So if element is greater it would be the last
    
    while low <= high {
        let mid = (low + high) / 2
        // maybe an answer
        if arr[mid] >= targetElement {
            ans = arr[mid]
            // look for smaller index on the left
            high = mid - 1
        } else {
            low = mid + 1 // look on the right
        }
    }
    return ans
}

func findFloor(_ arr: [Int], _ targetElement: Int) -> Int {
    let arrayCount = arr.count
    var low = 0
    var high = arrayCount - 1
    var ans = arrayCount//So if element is greater it would be the last
    
    while low <= high {
        let mid = (low + high) / 2
        // maybe an answer
        if arr[mid] <= targetElement {
            ans = arr[mid]
            // look for smaller index on the left
            low = mid + 1 // look on the right
        } else {
            high = mid - 1; // look on the right
        }
    }
    return ans
}

var inputBinaryArray = [3, 4, 4, 7, 8, 10]
let targetEl = 5
let floorFound = findFloor(inputBinaryArray, targetEl)
let ceilFound = findCeil(inputBinaryArray, targetEl)

print("floorFound ", floorFound) // 4
print("ceilFound ", ceilFound) // 7

Leave a Comment

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