Floor and Ceiling in a Sorted Array

Floor and Ceiling in a Sorted Array is a classic binary-search warm-up. It takes the plain "find this value" search and bends it into "find the closest value on each side" — the move behind range queries, autocomplete bounds, and price-tier lookups.

The slow way first

The obvious idea: scan the whole array and keep the best candidate on each side. For every element, if it is <= x and bigger than the floor so far, it becomes the new floor; if it is >= x and smaller than the ceil so far, it becomes the new ceil. That works, but it touches every element — O(n) — and completely ignores the gift the problem handed us: the array is sorted.

The question to ask: the array is sorted, so can I jump instead of crawl? Yes — binary search lets us halve the search space each step and land on both answers in O(log n).

The idea: one binary search that records both

Run a single binary-search pass. At the middle element a[mid], only two cases matter:

• If a[mid] <= x, it is a valid floor candidate. Save it, then go right — a larger value that is still <= x can only be further right.
• If a[mid] >= x (here, strictly greater), it is a valid ceil candidate. Save it, then go left — a smaller value that is still >= x can only be further left.

The key insight: every time we move, we overwrite the candidate with a strictly better one. Whatever value sits in floor and ceil when the window empties out is the answer — no extra comparison needed.

Walk through it

Step through the animation. The pointer mid lands in the current window, we compare a[mid] to 5, and based on the result we record one answer and discard half the array (dimmed). Watch the two labels: floor only ever grows toward x from below, and ceil only ever shrinks toward x from above. When lo passes hi, the labels hold 2 and 8.

Pseudocode

floor = ceil = None
lo, hi = 0, last index
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] <= x:
        floor = a[mid]            # valid floor, maybe a bigger one is to the right
        lo = mid + 1
    else:
        ceil = a[mid]             # valid ceil, maybe a smaller one is to the left
        hi = mid - 1
return floor, ceil

The Python solution

def floor_ceil(a, x):
    floor = ceil = None
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            floor = a[mid]
            lo = mid + 1
        else:
            ceil = a[mid]
            hi = mid - 1
    return floor, ceil

• floor and ceil start as None so a missing side stays None (e.g. x smaller than everything has no floor).
• lo and hi bracket the current search window; the loop runs while it is non-empty.
• mid = (lo + hi) // 2 is the middle index of that window.
• When a[mid] <= x, line 7 records it as the floor and line 8 moves right to hunt for something bigger but still <= x.
• When a[mid] > x, line 10 records it as the ceil and line 11 moves left to hunt for something smaller but still >= x.
• If x is itself in the array, it gets caught by the <= x branch as the floor; the ceil branch then closes in until ceil also equals x.

Complexity

We use only a handful of variables, so the extra space is O(1). The win comes from exploiting the sorted order: O(n) becomes O(log n), and we still get both boundaries in a single pass.

When this pattern shows up

Practice