Ceil The Floor | Binary Search Implementation

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.

Because the array is ordered, a single binary-search pass can locate both values in O(log n) time.

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 than x (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

Code Explanation

• Two comparisons per element update floor and ceil 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:

1. low, high bound the current window.
2. mid = (low + high) // 2.
3. If a[mid] == x → exact match: both floor and ceil are x.
4. If a[mid] > x → a[mid] is a candidate ceil; move left (high = mid – 1) to search for a smaller one.
5. If a[mid] < x → a[mid] is a candidate floor; move right (low = mid + 1) to look for a larger one.
6. Loop until low > high; remaining floor and ceil 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

Code 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.