Ceiling in a sorted array

We have a sorted array and a value x, the ceiling of x is the smallest element in an array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume that the array is sorted in non-decreasing order. Our task is to write efficient functions to find the floor and ceiling of x.

For example,

Input array {1, 2, 8, 10, 10, 12, 19}

For x = 0:    floor doesn't exist in the array,  ceil  = 1

For x = 1:    floor  = 1,  ceil  = 1

For x = 5:    floor  = 2,  ceil  = 8

For x = 20:   floor  = 19,  ceil doesn't exist in the array

Approach

1. Finding the Floor of x:

1. Initialize two pointers, left and right, to point to the start and end of the array, respectively.
2. Initialize a variable floor to -1. This will store the floor value of x.
3. Enter a loop that continues as long as left is less than or equal to right.
4. Calculate the middle index mid as (left + right) / 2.
5. Compare the element at index mid with x. There are three possibilities:

• If the element at mid is equal to x, return x as both the floor and ceiling are x.
• If the element at mid is less than x, update floor to the element at mid and move the left pointer to mid + 1 to potentially find a larger floor.
• If the element at mid is greater than x, move the right pointer to mid - 1 to potentially find a smaller floor.

6. Continue the loop until left is no longer less than or equal to right.
7. Return the floor as the floor value of x.

2. Finding the Ceiling of x:

1. The approach for finding the ceiling is similar to finding the floor, with a few changes:
2. Initialize a variable ceiling to -1. This will store the ceiling value of x.
3. In the comparison step, if the element at mid is greater than x, update ceiling to the element at mid and move the right pointer to mid - 1 to potentially find a smaller ceiling.
4. Continue the loop until left is no longer less than or equal to right.
5. Return the ceiling as the ceiling value of x.

Both the floor and ceiling are found using binary search by narrowing down the search range until a match is found or the pointers cross each other.

Complexity

• Time Complexity: O(log n), where 'n' is the length of the input array. The time complexity for finding the floor and ceiling using binary search is O(log n)
• Space Complexity: O(1), because the code uses a fixed number of variables

Code

#Java Code

public class FloorCeilingInSortedArray {

    public static int findFloor(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        int floor = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (sortedArray[mid] == target) {
                return sortedArray[mid]; // Target is present in the array, so it's the floor as well
            } else if (sortedArray[mid] < target) {
                floor = sortedArray[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return floor;
    }

    public static int findCeiling(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        int ceiling = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (sortedArray[mid] == target) {
                return sortedArray[mid]; // Target is present in the array, so it's the ceiling as well
            } else if (sortedArray[mid] < target) {
                left = mid + 1;
            } else {
                ceiling = sortedArray[mid];
                right = mid - 1;
            }
        }

        return ceiling;
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 8, 10, 10, 12, 19};
        int target = 5;

        int floor = findFloor(sortedArray, target);
        int ceiling = findCeiling(sortedArray, target);

        System.out.println("Floor of " + target + " is: " + floor);
        System.out.println("Ceiling of " + target + " is: " + ceiling);
    }
}

Output

Floor of 5 is: 2
Ceiling of 5 is: 8