Find Floor and Ceiling in Sorted Array Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

void findFloorCeil(int arr[], int n, int x, int* floor, int* ceil) {
    int low = 0, high = n - 1;
    *floor = -1;
    *ceil = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            *floor = *ceil = arr[mid];
            return;
        } else if (arr[mid] < x) {
            *floor = arr[mid];
            low = mid + 1;
        } else {
            *ceil = arr[mid];
            high = mid - 1;
        }
    }
}

int main() {
    int arr[] = {1, 2, 4, 6, 10, 12};
    int x = 5, floor, ceil;
    int n = sizeof(arr) / sizeof(arr[0]);
    findFloorCeil(arr, n, x, &floor, &ceil);
    printf("Floor: %d, Ceil: %d\n", floor, ceil);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target value is found at the mid index during the first iteration of binary search, requiring no further comparisons.
Average CaseO(log n)The binary search halves the search space in each step until the correct floor and ceiling values are found.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...