Last Updated: 8 Jul, 2021
Ceil The Floor
Moderate
Asked in company
You're given a sorted array 'a' of 'n' integers and an integer 'x'.
Find the floor and ceiling of 'x' in 'a[0..n-1]'.
Note:
Floor of 'x' is the largest element in the array which is smaller than or equal to 'x'.
Ceiling of 'x' is the smallest element in the array greater than or equal to 'x'.
Example:
Input:
n=6, x=5, a=[3, 4, 7, 8, 8, 10]
Output:
4
Explanation:
The floor and ceiling of 'x' = 5 are 4 and 7, respectively.
Input Format :
The first line contains two integers, ‘n’ and 'x', where n represents the size of the array.
The next line contains 'n' integers, denoting the elements of the given array.
Output Format :
Return two integers, the floor and ceiling of 'x'.
Note :
You are not required to print anything; it has already been handled. Just implement the function.
Approaches
Simply iterate all the elements of the array. While iterating, check each number for floor and ceil.
The steps are as follows:
- Initialize ‘FLOOR’ with -1 and ‘CEIL’ with positive infinity.
- Iterate the given array.
- If ai >= X and ai < CEIL
- CEIL = ai
- If ai <= X and ai > FLOOR
- FLOOR = ai
- If ai >= X and ai < CEIL
- If CEIL is still positive infinity:
- CEIL = -1
- Return the pair of FLOOR and CEIL.
This question is similar to finding lower_bound of X, Hence we can use binary search to solve it on our own.
Start from a search space of the entire array, each time reduce the search space to half, continue doing this until the search space size becomes 0.
The steps are as follows:
- Initialize Ans = -1
- Initialize L = 0 and H = N-1 (initial search space) and Mid = (L+H)/2
- If the middle element of search space is greater than equal to X, then store this value(aMid) in ‘Ans’ and continue the search on the left half. ie: set H = MID - 1
- If the middle element of search space is lesser than X, then continue the search on the right half. ie: set L= Mid+1
- Continue the search till the L<=H condition is satisfied.
- Finally, return Ans.
Similar problems