To find the floor and ceiling of a given number x
in a sorted array, we use an efficient method called Binary Search. This method reduces the search space in half at each step, making it much faster than checking each element one by one.
Key Definitions
- 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
.
How the Binary Search Approach Works
We start by looking at the entire array and gradually narrow down the search range using two pointers: low
(beginning of the array) and high
(end of the array). At each step, we check the middle element:
Case 1: If the middle element exactly matches the number x
we are looking for, then it is both the floor and the ceiling—so we can return it right away.
Case 2: If the middle element is smaller than x
, it means this number could be the floor (since it's less than or equal to x
). But maybe there's an even closer number to x
further to the right, so we move our low
pointer to the right and keep searching.
Case 3: On the other hand, if the middle element is greater than x
, it could be the ceiling (the smallest number greater than or equal to x
). We move the high
pointer to the left and continue searching to find a smaller suitable value.
We keep repeating this process—checking the middle, updating floor or ceil candidates, and narrowing the search space—until the pointers cross each other. At that point, we’ve either found an exact match or the closest floor and ceiling values.
Why This Works
Since the input array is sorted, binary search helps us avoid scanning every element. Instead, we eliminate half of the remaining elements with every comparison.