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 |
#include <stdio.h> // 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(void) { int arr[] = { 1, 4, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i <= 10; i++) { printf("Number %2d -> ", i); printf("ceiling is %2d, ", getCeil(arr, 0, n - 1, i)); printf("floor is %2d\n", getFloor(arr, 0, n - 1, i)); } return 0; } |

## Java

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 95 96 97 98 |
class FindFloorCeil { // Function to find ceil of x in sorted array A[left..right] // i.e. smallest integer greater than or equal to x public static int getCeil(int[] A, int left, int right, int x) { // search space is A[left..right] // if x is less than equal to leftest element in search // space, the leftest element is the ceil if (x <= A[left]) { return A[left]; } // if x is more than rightest element in the search space, // its ceil doesn't exists if (x > A[right]) { return -1; } // find middle index int mid = (left + right) / 2; // if x is equal to mid element, it is the ceil if (A[mid] == x) { return A[mid]; } // if x is more than the mid element, ceil exists in // right sub-array A[mid+1..right] else if (A[mid] < x) { return getCeil(A, mid + 1, right, x); } // if x is less than the mid element, ceil exists in left // sub-array A[left..mid](Note - mid element can also be ceil) else { return getCeil(A, left, mid, x); } } // Function to find floor of x in sorted array A[left..right] // i.e. largest integer less than or equal to x public static int getFloor(int[] A, int left, int right, int x) { // search space is A[left..right] // if x is less than the leftest element in search // space, its floor doesn't exists if (x < A[left]) { return -1; } // if x is more than equal to the rightest element in // the search space, it is the floor if (x >= A[right]) { return A[right]; } // find middle index int mid = (left + right) / 2; // this check is placed to handle infinite loop for // call getFloor(A, mid, right, x); if (mid == left) { return A[left]; } // if x is equal to mid element, it is the floor if (A[mid] == x) { return A[mid]; } // if x is more than the mid element, floor exists in right // sub-array A[mid..right](Note - mid element can also be floor) else if (A[mid] < x) { return getFloor(A, mid, right, x); } // if x is less than the mid element, floor exists in // left sub-array A[left..mid-1] else { return getFloor(A, left, mid - 1, x); } } public static void main(String[] args) { int[] A = { 1, 4, 6, 8, 9 }; for (int i = 0; i <= 10; i++) { System.out.print("Number " + i + " -> "); System.out.print("ceiling is " + getCeil(A, 0, A.length - 1, i) + ", "); System.out.println("floor is " + getFloor(A, 0, A.length - 1, i)); } } } |

`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

In the recursion solution, don’t we need to ensure that the function is not called or does not process anything when low > high?