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

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 94 |
#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; } // main function 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

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

## Leave a Reply