Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Floor & Ceiling in Sorted Array

EASYProblemSolveExternal Links

Description

Given a sorted array of integers arr[] and an integer x, find the floor and ceiling of x in the array.

  • Floor of x is the largest element in the array that is less than or equal to x. Return the index of this element, or -1 if no such element exists.

  • Ceiling of x is the smallest element in the array that is greater than or equal to x. Return the index of this element, or -1 if no such element exists.

Return the result as a pair of indices: [floor_index, ceiling_index].

Examples

Example 1

Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 5

Output: [1, 2]

Explanation:

  • Floor of 5: The largest element ≤ 5 is 2 (at index 1). Elements 1 and 2 are both ≤ 5, but 2 is the largest among them.
  • Ceiling of 5: The smallest element ≥ 5 is 8 (at index 2). Elements 8, 10, 10, 12, 19 are all ≥ 5, but 8 is the smallest among them.

Example 2

Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 20

Output: [6, -1]

Explanation:

  • Floor of 20: The largest element ≤ 20 is 19 (at index 6). All elements are ≤ 20, and 19 is the largest.
  • Ceiling of 20: No element is ≥ 20 in the array. So ceiling is -1.

Example 3

Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 0

Output: [-1, 0]

Explanation:

  • Floor of 0: No element is ≤ 0 in the array. So floor is -1.
  • Ceiling of 0: The smallest element ≥ 0 is 1 (at index 0).

Example 4

Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 10

Output: [4, 3]

Explanation:

  • Floor of 10: The largest element ≤ 10 is 10 itself. Since there are duplicates, we pick the last occurrence of 10, which is at index 4.
  • Ceiling of 10: The smallest element ≥ 10 is 10 itself. We pick the first occurrence of 10, which is at index 3.

Constraints

  • 1 ≤ arr.size() ≤ 10^6
  • 1 ≤ arr[i] ≤ 10^6
  • 0 ≤ x ≤ 10^6
  • The array is sorted in non-decreasing order.

Editorial

Brute Force

Intuition

The most straightforward approach is to scan the entire array linearly and keep track of the best candidates for both floor and ceiling.

For the floor: Walk through the array and keep updating the answer whenever you find an element that is ≤ x. Because the array is sorted in non-decreasing order, a later valid element will always be ≥ the previous one, so the last valid element we encounter will be the largest one ≤ x.

For the ceiling: Walk through the array and return the first element that is ≥ x. Because the array is sorted, the first such element is automatically the smallest one ≥ x.

Think of it like checking items on a shelf arranged in ascending price. For the floor (biggest price ≤ your budget), you walk along and keep noting the latest affordable item. For the ceiling (cheapest item ≥ your budget), you stop at the first item that meets or exceeds your budget.

Step-by-Step Explanation

Let's trace through arr = [1, 2, 8, 10, 10, 12, 19], x = 5:

Finding Floor (largest element ≤ x):

  • i = 0: arr[0] = 1, 1 ≤ 5? YES → floor_idx = 0
  • i = 1: arr[1] = 2, 2 ≤ 5? YES → floor_idx = 1 (updated, 2 > 1)
  • i = 2: arr[2] = 8, 8 ≤ 5? NO → stop (since array is sorted, all remaining elements will be > 5 too)
  • Floor answer: index 1 (value 2)

Finding Ceiling (smallest element ≥ x):

  • i = 0: arr[0] = 1, 1 ≥ 5? NO
  • i = 1: arr[1] = 2, 2 ≥ 5? NO
  • i = 2: arr[2] = 8, 8 ≥ 5? YES → ceiling_idx = 2, stop immediately
  • Ceiling answer: index 2 (value 8)

Result: [1, 2]

Linear Scan — Finding Floor and Ceiling of x = 5 — Two passes through the array: first to find the floor (largest element ≤ x), then to find the ceiling (smallest element ≥ x).

Algorithm

Finding Floor:

  1. Initialize floor_idx = -1.
  2. Iterate from i = 0 to n - 1:
    a. If arr[i] ≤ x, update floor_idx = i.
    b. If arr[i] > x, break (remaining elements are all > x).
  3. Return floor_idx.

Finding Ceiling:

  1. Initialize ceiling_idx = -1.
  2. Iterate from i = 0 to n - 1:
    a. If arr[i] ≥ x, set ceiling_idx = i and break.
  3. Return ceiling_idx.

Combined: Return [floor_idx, ceiling_idx].

Code

#include <vector>
#include <utility>
using namespace std;

class Solution {
public:
    pair<int, int> floorAndCeiling(vector<int>& arr, int x) {
        int n = arr.size();
        int floorIdx = -1, ceilIdx = -1;
        
        // Find floor: largest element <= x
        for (int i = 0; i < n; i++) {
            if (arr[i] <= x) {
                floorIdx = i;
            } else {
                break;
            }
        }
        
        // Find ceiling: smallest element >= x
        for (int i = 0; i < n; i++) {
            if (arr[i] >= x) {
                ceilIdx = i;
                break;
            }
        }
        
        return {floorIdx, ceilIdx};
    }
};
class Solution:
    def floorAndCeiling(self, arr, x):
        n = len(arr)
        floor_idx = -1
        ceil_idx = -1
        
        # Find floor: largest element <= x
        for i in range(n):
            if arr[i] <= x:
                floor_idx = i
            else:
                break
        
        # Find ceiling: smallest element >= x
        for i in range(n):
            if arr[i] >= x:
                ceil_idx = i
                break
        
        return [floor_idx, ceil_idx]
class Solution {
    public int[] floorAndCeiling(int[] arr, int x) {
        int n = arr.length;
        int floorIdx = -1, ceilIdx = -1;
        
        // Find floor: largest element <= x
        for (int i = 0; i < n; i++) {
            if (arr[i] <= x) {
                floorIdx = i;
            } else {
                break;
            }
        }
        
        // Find ceiling: smallest element >= x
        for (int i = 0; i < n; i++) {
            if (arr[i] >= x) {
                ceilIdx = i;
                break;
            }
        }
        
        return new int[]{floorIdx, ceilIdx};
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, both the floor and ceiling scans traverse the entire array. For example, if x is larger than all elements, the floor scan visits every element. If x is smaller than all elements, the ceiling scan starts at index 0 (constant), but the floor scan visits no elements. Overall worst case is O(n).

Space Complexity: O(1)

Only a few integer variables are used. No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force linear scan ignores the sorted property of the array. We are doing O(n) work when the sorted structure allows O(log n).

Consider the floor search: if we check the middle element and it is ≤ x, we know it's a valid floor candidate. But there might be a larger valid element to the right — so we search right while keeping this as our best answer so far. If the middle element is > x, it's too big, so the floor must be in the left half. This halving of the search space at each step is binary search.

Similarly for ceiling: if the middle element is ≥ x, it's a valid ceiling candidate, but we search left to find a potentially smaller valid element. If the middle element is < x, it's too small, so the ceiling must be in the right half.

Both floor and ceiling can be found independently using binary search, each taking O(log n) time. Combined: O(log n) + O(log n) = O(log n). For n = 10^6, this means ~20 comparisons each instead of up to 10^6.

Optimal Approach - Binary Search

Intuition

We solve floor and ceiling as two independent binary search problems:

Floor Binary Search (largest element ≤ x):

  • If arr[mid] ≤ x: this is a valid floor candidate. Record it and search right for a potentially larger valid element (we want the largest such element).
  • If arr[mid] > x: too big for floor. Search left for smaller values.

Ceiling Binary Search (smallest element ≥ x):

  • If arr[mid] ≥ x: this is a valid ceiling candidate. Record it and search left for a potentially smaller valid element (we want the smallest such element).
  • If arr[mid] < x: too small for ceiling. Search right for larger values.

Notice the symmetry: floor searches right after finding a candidate (to find a bigger valid element), while ceiling searches left (to find a smaller valid element). This makes sense because floor wants the maximum of valid elements and ceiling wants the minimum.

Step-by-Step Explanation

Let's trace arr = [1, 2, 8, 10, 10, 12, 19], x = 5:

Binary Search for Floor (largest ≤ 5):

Steplowhighmidarr[mid]Check ≤ 5?Action
106310NOhigh = 2
20212YES → floor = 1low = 2
32228NOhigh = 1
Endlow > high → Return floor = 1

Binary Search for Ceiling (smallest ≥ 5):

Steplowhighmidarr[mid]Check ≥ 5?Action
106310YES → ceil = 3high = 2
20212NOlow = 2
32228YES → ceil = 2high = 1
Endlow > high → Return ceil = 2

Result: [1, 2]

Binary Search for Floor — Largest Element ≤ 5 — When arr[mid] ≤ x, record it as a floor candidate and search right for a larger valid element. When arr[mid] > x, search left.

Binary Search for Ceiling — Smallest Element ≥ 5 — When arr[mid] ≥ x, record it as a ceiling candidate and search left for a smaller valid element. When arr[mid] < x, search right.

Algorithm

Finding Floor using Binary Search:

  1. Initialize low = 0, high = n - 1, floor_idx = -1.
  2. While low ≤ high:
    a. Compute mid = low + (high - low) / 2.
    b. If arr[mid] ≤ x: this is a valid candidate. Set floor_idx = mid and search right: low = mid + 1.
    c. Else: search left: high = mid - 1.
  3. Return floor_idx.

Finding Ceiling using Binary Search:

  1. Initialize low = 0, high = n - 1, ceil_idx = -1.
  2. While low ≤ high:
    a. Compute mid = low + (high - low) / 2.
    b. If arr[mid] ≥ x: this is a valid candidate. Set ceil_idx = mid and search left: high = mid - 1.
    c. Else: search right: low = mid + 1.
  3. Return ceil_idx.

Combined: Return [floor_idx, ceil_idx].

Code

#include <vector>
#include <utility>
using namespace std;

class Solution {
public:
    pair<int, int> floorAndCeiling(vector<int>& arr, int x) {
        int n = arr.size();
        
        int floorIdx = findFloor(arr, n, x);
        int ceilIdx = findCeiling(arr, n, x);
        
        return {floorIdx, ceilIdx};
    }
    
private:
    int findFloor(vector<int>& arr, int n, int x) {
        int low = 0, high = n - 1;
        int answer = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] <= x) {
                answer = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return answer;
    }
    
    int findCeiling(vector<int>& arr, int n, int x) {
        int low = 0, high = n - 1;
        int answer = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] >= x) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return answer;
    }
};
class Solution:
    def floorAndCeiling(self, arr, x):
        floor_idx = self.findFloor(arr, x)
        ceil_idx = self.findCeiling(arr, x)
        return [floor_idx, ceil_idx]
    
    def findFloor(self, arr, x):
        low, high = 0, len(arr) - 1
        answer = -1
        
        while low <= high:
            mid = low + (high - low) // 2
            
            if arr[mid] <= x:
                answer = mid
                low = mid + 1
            else:
                high = mid - 1
        
        return answer
    
    def findCeiling(self, arr, x):
        low, high = 0, len(arr) - 1
        answer = -1
        
        while low <= high:
            mid = low + (high - low) // 2
            
            if arr[mid] >= x:
                answer = mid
                high = mid - 1
            else:
                low = mid + 1
        
        return answer
class Solution {
    public int[] floorAndCeiling(int[] arr, int x) {
        int floorIdx = findFloor(arr, x);
        int ceilIdx = findCeiling(arr, x);
        return new int[]{floorIdx, ceilIdx};
    }
    
    private int findFloor(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int answer = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] <= x) {
                answer = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return answer;
    }
    
    private int findCeiling(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int answer = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] >= x) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(log n)

We run two binary searches, each taking O(log n) time. The total is O(log n) + O(log n) = O(2 · log n) = O(log n). For n = 10^6, each binary search performs about 20 comparisons, for a total of ~40 comparisons — compared to up to 2 × 10^6 with brute force.

Space Complexity: O(1)

Each binary search uses three integer variables (low, high, answer). No additional data structures are needed. Space usage is constant.