[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