Understanding the Problem
We are given a sorted array and a number x
.
Our task is to find two special values:
- Floor – the largest number in the array that is less than or equal to
x
.
- Ceiling – the smallest number in the array that is greater than or equal to
x
.
This means we’re looking for the closest values that "hug" x
from below and above.
The solution must work efficiently, especially for large arrays.
Step-by-Step Plan Using an Example
Example
Array = [1, 3, 5, 7, 9]
x = 6
Here, floor(6)
should be 5 and ceiling(6)
should be 7.
Step 1: Use Binary Search
Since the array is sorted, we’ll use binary search to reduce our work by half at every step.
We maintain two pointers: low
and high
. At each step, we calculate mid
and compare the middle element with x
.
Step 2: Apply the Three Cases
- If arr[mid] == x → We found an exact match. Both floor and ceiling are
x
.
- If arr[mid] < x → This could be a floor. We move
low = mid + 1
.
- If arr[mid] > x → This could be a ceiling. We move
high = mid - 1
.
Step 3: Track Closest Values
During the search, we keep updating two variables:
floor
gets updated when we find a number ≤ x
ceiling
gets updated when we find a number ≥ x
Final Result
When the loop ends, floor
and ceiling
will hold our answers.
Incorporating Edge Cases
Let’s handle some special situations:
- If
x
is smaller than all elements in the array → floor doesn’t exist, only ceiling.
- If
x
is greater than all elements → ceiling doesn’t exist, only floor.
- If
x
exactly matches an element → both floor and ceiling are x
.
Our code needs to check and return null
or a special value (like -1
) when a floor or ceiling doesn’t exist.
Why Binary Search Works
Binary Search divides the search space in half at every step, so it runs in O(log n)
time.
This makes it very efficient for large arrays.
Since the array is sorted, we never miss any candidates—we just have to make the right decisions at each midpoint.
Beginner Tip
Always test your algorithm with:
- Values smaller than the first element
- Values larger than the last element
- Values in the middle
- Exact matches
This builds confidence that your logic is covering all edge cases.
Comments
Loading comments...