Find Floor and Ceiling in Sorted Array Binary Search Approach

Problem Statement❯

Given a sorted array of integers and a target number x, your task is to find the floor and ceil of x in the array.

The floor of x is the greatest number in the array that is less than or equal to x.
The ceil of x is the smallest number in the array that is greater than or equal to x.

If the floor or ceil does not exist, return -1 for that value.

Examples❯

Input Array	Key (x)	Floor	Ceil	Description
[10, 20, 30, 40, 50]	35	30	40	35 lies between 30 and 40
[10, 20, 30, 40, 50]	10	10	10	Exact match, floor and ceil are the same
[10, 20, 30, 40, 50]	5	-1	10	No floor exists, ceil is the first element
[10, 20, 30, 40, 50]	55	50	-1	Floor exists, no ceil since key is greater than all
[10, 20, 30, 40, 50]	25	20	30	25 lies between 20 and 30
[15]	15	15	15	Single element match
[15]	10	-1	15	Single element greater than key
[15]	20	15	-1	Single element less than key

Visualization Player

Solution❯

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.

Algorithm Steps❯

Given a sorted array arr and a target value x.
Initialize floor = -1 and ceil = -1.
Use binary search to find floor:
→ While low ≤ high, compute mid.
→ If arr[mid] == x, both floor and ceil are arr[mid]. Return.
→ If arr[mid] < x, update floor = arr[mid], search right.
→ If arr[mid] > x, update ceil = arr[mid], search left.
Continue until low > high.
Return the computed floor and ceil.

Code

Python

JavaScript

Java

C++

def find_floor_ceil(arr, x):
    low, high = 0, len(arr) - 1
    floor, ceil = -1, -1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            # Exact match is both floor and ceil
            return arr[mid], arr[mid]
        elif arr[mid] < x:
            # Current element could be a candidate for floor
            floor = arr[mid]
            low = mid + 1  # Search in the right half
        else:
            # Current element could be a candidate for ceil
            ceil = arr[mid]
            high = mid - 1  # Search in the left half

    return floor, ceil

# Sample Input
arr = [1, 2, 4, 6, 10, 12]
x = 5
print("Floor and Ceil:", find_floor_ceil(arr, x))

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	The target value is found at the mid index during the first iteration of binary search, requiring no further comparisons.
Average Case	O(log n)	The binary search halves the search space in each step until the correct floor and ceiling values are found.
Worst Case	O(log n)	In the worst case, the search continues until only one element remains, after which the floor and ceiling values are determined.

Space Complexity❯

O(1)

Explanation: The algorithm operates using a constant number of variables (like low, high, mid, floor, ceil), without requiring additional memory.

⬅ Previous TopicSearch Insert Position in Sorted Array (Lower Bound Approach)

Next Topic ⮕First Occurrence in a Sorted Array

Comments

Loading comments...