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

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <iostream> using namespace std; // Function to find ceil of x in sorted array arr[0..n-1] // i.e. smallest integer greater than or equal to x int getCeil(int arr[], int n, int x) { // search space is A[low..high] int low = 0, high = n - 1, mid; // initialize ceil to -1 int ceil = -1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space mid = (low + high) / 2; // if x is equal to mid element, it is the ceil if (arr[mid] == x) return arr[mid]; // 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] else if (x < arr[mid]) { ceil = arr[mid]; high = mid - 1; } // if x is more than the mid element, ceil exists in the // right sub-array A[mid+1..high] else low = mid + 1; } return ceil; } // Function to find floor of x in sorted array arr[0..n-1] // i.e. largest integer less than or equal to x int getFloor(int arr[], int n, int x) { int low = 0, high = n - 1, mid; // initialize floor to -1 int floor = -1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space mid = (low + high) / 2; // if x is equal to mid element, it is the floor if (arr[mid] == x) return arr[mid]; // if x is less than the mid element, floor exists in the left // sub-array A[low..mid-1] else if (x < arr[mid]) high = 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] else { floor = arr[mid]; low = mid + 1; } } return floor; } // Find Floor and Ceil of a number in a sorted array int main() { int arr[] = { 1, 4, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i <= 10; i++) { cout << "Number " << i << " -> "; cout << "ceiling is " << getCeil(arr, n, i) << ", "; cout << "floor is " << getFloor(arr, n, i) << endl; } return 0; } |

**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)`

.

**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 🙂

## Leave a Reply