262. Floor and Ceiling
Core1000 ms256 MBSolved by 0%
Given n distinct integers in increasing order and a value x, print two
values separated by a space:
- the FLOOR: the largest value that is at most
x, orNoneif there is - none
- the CEILING: the smallest value that is at least
x, orNoneif there is - none
If x is present it is both its own floor and its own ceiling.
Both are one binary search each, and both are variations of the lower bound you have now written three times. The interesting part is the two cases where the answer does not exist, which are the ends of the array.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - All values are distinct and increasing.
Input
The first line contains two integers n and x.
The second line contains n distinct integers in increasing order.
Output
Print the floor and the ceiling separated by a space, using None where one does not exist.
Input5 5
1 2 8 10 11
Output2 8
Notehas x absent, with both neighbours existing
Input5 1
1 2 8 10 11
Output1 1
Notehas x present at the start, so it is both answers
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.