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

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 |
#include <iostream> using namespace std; // Function to find ceil of x in sorted array arr[low..high] // i.e. smallest integer greater than or equal to x int getCeil(int arr[], int low, int high, int x) { // search space is A[low..high] // if x is less than equal to lowest element in search // space, the lowest element is the ceil if (x <= arr[low]) return arr[low]; // if x is more than highest element in the search space, // its ceil doesn't exists if (x > arr[high]) return -1; // find middle index int 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 more than the mid element, ceil exists in // right sub-array A[mid+1..high] else if (arr[mid] < x) return getCeil(arr, mid + 1, high, x); // if x is less than the mid element, ceil exists in left // sub-array A[low..mid](Note - mid element can also be ceil) else return getCeil(arr, low, mid, x); } // Function to find floor of x in sorted array arr[low..high] // i.e. largest integer less than or equal to x int getFloor(int arr[], int low, int high, int x) { // search space is A[low..high] // if x is less than the lowest element in search // space, its floor doesn't exists if (x < arr[low]) return -1; // if x is more than equal to the highest element in // the search space, it is the floor if (x >= arr[high]) return arr[high]; // find middle index int mid = (low + high) / 2; // this check is placed to handle infinite loop for // call getFloor(arr, mid, high, x); if (mid == low) return arr[low]; // if x is equal to mid element, it is the floor if (arr[mid] == x) return arr[mid]; // if x is more than the mid element, floor exists in right // sub-array A[mid..high](Note - mid element can also be floor) else if (arr[mid] < x) return getFloor(arr, mid, high, x); // if x is less than the mid element, floor exists in // left sub-array A[low..mid-1] else return getFloor(arr, low, mid - 1, x); } // 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, 0, n - 1, i) << ", "; cout << "floor is " << getFloor(arr, 0, n - 1, 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

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