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 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:
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]

 
C++ implementation –
 

Download   Run Code

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)).
Auxiliary space used by the program is O(1).

 
Exercise: Write recursive solution to find Floor and Ceil of a number

Thanks for reading.




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 🙂