# Find Floor and Ceil of a number in a sorted array

Given a sorted array of integers, find floor and ceil of a given number in it. The floor and ceil map the given number to the largest previous or the smallest following integer, respectively.

More precisely, for a number x `floor(x)` is the largest integer less than or equal to x and `ceiling(x)` is the smallest integer greater than or equal to x. For example,

Input:

A[] = [1, 4, 6, 8, 9]
Number – 0 to 10

Output:

Number 0 -> ceiling is 1, floor is -1
Number 1 -> ceiling is 1, floor is 1
Number 2 -> ceiling is 4, floor is 1
Number 3 -> ceiling is 4, floor is 1
Number 4 -> ceiling is 4, floor is 4
Number 5 -> ceiling is 6, floor is 4
Number 6 -> ceiling is 6, floor is 6
Number 7 -> ceiling is 8, floor is 6
Number 8 -> ceiling is 8, floor is 8
Number 9 -> ceiling is 9, floor is 9
Number 10 -> ceiling is -1, floor is 9

A simple solution would be to run a linear search on the array and find the largest integer in the array less than or equal to x and the smallest integer in the array greater than or equal to x. That would be the floor and ceiling of number x respectively. The problem with this approach is that its worst case time complexity is `O(n)`.

We can easily solve this problem in `O(log(n))` time by modifying Binary Search Algorithm. The basic idea remains the same. We find mid and recurse for left or right sub-array based on comparison result with the given number. Below is the complete algorithm –

`findCeil(A[low, high], x)`

Initialize ceil to -1 and iterate till our search space is exhausted

• if x is equal to mid element, it is the ceil
• if x is less than the mid element, ceil exists in the sub-array `A[low..mid]`. We update ceil to the mid element and reduce our search space to left subarray `A[low..mid-1]`
• if x is more than the mid element, ceil exists in the right sub-array `A[mid+1..high]`

`findFloor(A[low, high], x)`

Initialize floor to -1 and iterate till our search space is exhausted

• if x is equal to mid element, it is the floor
• if x is less than the mid element, floor exists in the left sub-array `A[low..mid-1]`
• if x is more than the mid element, floor exists in the sub-array `A[mid..high]`. We update floor to the mid element and reduce our search space to right subarray `A[mid+1..high]`

## Java

Output:

Number 0 -> ceiling is 1, floor is -1
Number 1 -> ceiling is 1, floor is 1
Number 2 -> ceiling is 4, floor is 1
Number 3 -> ceiling is 4, floor is 1
Number 4 -> ceiling is 4, floor is 4
Number 5 -> ceiling is 6, floor is 4
Number 6 -> ceiling is 6, floor is 6
Number 7 -> ceiling is 8, floor is 6
Number 8 -> ceiling is 8, floor is 8
Number 9 -> ceiling is 9, floor is 9
Number 10 -> ceiling is -1, floor is 9

The time complexity of above solution is `O(log(n))` and auxiliary space used by the program is `O(1)`.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂