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

C++

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)).

 
Exercise: Write Iterative 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.
 



 



Leave a Reply

Notify of
avatar
wpDiscuz