# Find Floor and Ceil of a number in a sorted array (Recursive solution)

Given a sorted array of integers, find floor and ceil of a given number in it. The floor and ceiling 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:

arr = [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)`

• if x is less than equal to `A[low]`, `A[low]` is the ceil.
• if x is more than `A[high]`, its ceil doesn’t exists.
• if x is equal to mid element, it is the ceil.
• if x is more than the mid element, ceil exists in right sub-array `A[mid+1..high]`.
• if x is less than the mid element, ceil exists in left sub-array `A[low..mid]`. Here we include mid as part of left sub-array as mid element can also be ceil.

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

• if x is less than `A[low]`, its floor doesn’t exists.
• if x is more than equal to the `A[high]`, it is the floor.
• if x is equal to mid element, it is the floor.
• if x is more than the mid element, floor exists in right sub-array `A[mid..high]`. Here we include mid as part of right sub-array as mid element can also be floor.
• if x is less than the mid element, floor exists in left sub-array `A[low..mid-1]`.

## 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

Time complexity of above solution is `O(log(n))`.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.