Floor and Ceil

Here are the detailed commercial-grade notes for the problem Ceiling and Floor in a Sorted Array, suitable for instructional and commercial use.

Problem Link

ceiling-in-a-sorted-array

Problem Statement

You are given a sorted array a of n integers and an integer x. Your task is to find both the floor and the ceiling of x in the array.

• Floor of x: the largest element in the array less than or equal to x.

• Ceiling of x: the smallest element in the array greater than or equal to x.

Return both values in an array of the form [floor, ceil].

Examples:

• Input: n = 6, x = 5, a = [3, 4, 7, 8, 8, 10]
  Output: [4, 7]

• Input: n = 6, x = 10, a = [1, 2, 3, 4, 5, 6]
  Output: [6, -1] (no ceiling)

• Input: n = 6, x = 0, a = [1, 2, 3, 4, 5, 6]
  Output: [-1, 1] (no floor)

Intuition

The array is sorted, which suggests using binary search to find the floor and ceiling efficiently in O(log n) time.

• If the target x is found, both floor and ceiling are equal to x.

• If not found, the current bounds of binary search (start and end) will help derive the floor and ceiling:

  • The floor will be at index end

  • The ceiling will be at index start

Approach

1. Initialize pointers:

   • start = 0, end = n - 1

2. Perform binary search:

   • If a[mid] == x, return [x, x]

   • If a[mid] > x, update end = mid - 1

   • If a[mid] < x, update start = mid + 1

3. After loop:

   • If end >= 0 and start < n, return [a[end], a[start]]

   • If end < 0, it means there’s no element ≤ x, so floor is -1

   • If start == n, it means there’s no element ≥ x, so ceiling is -1

Code in Java

public class Solution {
    public static int[] getFloorAndCeil(int[] a, int n, int x) {
        int start = 0;
        int end = a.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (a[mid] == x) {
                return new int[]{a[mid], a[mid]};
            } else if (a[mid] > x) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        if (end != -1 && start != a.length) {
            return new int[]{a[end], a[start]};
        }

        if (end == -1) {
            return new int[]{-1, a[start]};
        } else {
            return new int[]{a[end], -1};
        }
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  The array is searched using binary search.

• Space Complexity: O(1)
  Only constant extra space is used.

Dry Run

Input:

a = [3, 4, 7, 8, 8, 10], x = 5

Steps:

• start = 0, end = 5

• mid = 2, a[2] = 7 → 7 > 5 → end = 1

• mid = 0, a[0] = 3 → 3 < 5 → start = 1

• mid = 1, a[1] = 4 → 4 < 5 → start = 2

Loop ends with start = 2, end = 1

• Floor = a[1] = 4, Ceiling = a[2] = 7

Output: [4, 7]

Conclusion

This problem is a classic variation of binary search where instead of simply locating a value, we extract boundary values (floor and ceiling) based on binary search termination indices. Understanding the relationship between start and end post-search is key to solving such problems efficiently in logarithmic time.