For a sorted array a[]
of length n
and a value x
, you must return both:
- Floor – the greatest element ≤
x
- Ceil – the smallest element ≥
x
If either does not exist, output -1
in its place.
Here’s the [Problem Link] to begin with.
a (sorted) | x | Floor | Ceil |
---|---|---|---|
[1, 2, 8, 10, 11, 12, 19] | 0 | -1 | 1 |
[1, 2, 8, 10, 11, 12, 19] | 5 | 2 | 8 |
[1, 2, 8, 10, 11, 12, 19] | 19 | 19 | 19 |
Because the array is ordered, a single binary-search pass can locate both values in O(log n)
time.
Contents:
[show]
Brute Force Solution (Linear Scan)
Intuition & Approach
- Walk through every element.
- Track the largest value not exceeding
x
(floor) and the smallest value not less thanx
(ceil) as you go.
Code Implementation
def getFloorAndCeil(a, n, x):
floor = -1 # greatest value ≤ x found so far
ceil = -1 # smallest value ≥ x found so far
for num in a: # linear scan
if num <= x:
if floor == -1 or num > floor:
floor = num
if num >= x:
if ceil == -1 or num < ceil:
ceil = num
return floor, ceil
PythonCode Explanation
- Two comparisons per element update
floor
andceil
whenever a better candidate is seen. - After checking all
n
items, both answers are finalized.
Time & Space Complexity
- Time:
O(n)
– one full pass over the array. - Space:
O(1)
– only two extra variables.
Conclusion
Easy to implement but too slow for large arrays when a binary-search alternative exists.
Optimal Solution (Single Binary Search)
Intuition & Approach
Use binary search to shrink the search space while simultaneously tracking best‐so‐far floor and ceil:
low
,high
bound the current window.mid = (low + high) // 2
.- If
a[mid] == x
→ exact match: both floor and ceil arex
. - If
a[mid] > x
→a[mid]
is a candidate ceil; move left (high = mid – 1
) to search for a smaller one. - If
a[mid] < x
→a[mid]
is a candidate floor; move right (low = mid + 1
) to look for a larger one. - Loop until
low > high
; remainingfloor
andceil
are the answers.
Code Implementation
def getFloorAndCeil(a, n, x):
floor = -1 # best floor found so far (≤ x)
ceil = -1 # best ceil found so far (≥ x)
n = len(a) # array length (input n is not used here)
low, high = 0, n - 1 # binary-search boundaries
while low <= high:
mid = (low + high) // 2 # midpoint of current window
if a[mid] == x:
return [x, x] # exact match ⇒ floor = ceil = x
elif a[mid] > x:
ceil = a[mid] # update candidate ceil
high = mid - 1 # search smaller indices for a tighter ceil
else: # a[mid] < x
floor = a[mid] # update candidate floor
low = mid + 1 # search larger indices for a tighter floor
return [floor, ceil] # return final floor and ceil
PythonCode Explanation
floor
captures the largest element encountered that’s still ≤x
.ceil
holds the smallest element encountered that’s still ≥x
.- Each comparison discards half of the remaining indices, ensuring logarithmic performance.
Time & Space Complexity
- Time:
O(log n)
– classic binary-search behaviour. - Space:
O(1)
– constant auxiliary storage.
Conclusion
By adapting binary search to track both boundaries on the fly, we compute floor and ceil in logarithmic time with minimal code and memory, meeting the optimal efficiency for this problem.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.