Ceil & Floor

Find ceil and floor of number n in array.

Input:

array

number

Ceil is value in array which is just greater than n. If an element is equal to n exists that will be considered as ceil.

Floor is value in array which is just less than n. If an element is equal to n exists that will be considered as floor.

Assumption: array is sorted.

eg. 10 20 30 40 50 60 70 80 90 100

n = 55, ceil = 50; floor = 60

n = 40, ceil = 40; floor = 40

package jan21;

public class CeilFloor {
    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int n = 33;

        int low = 0, high = arr.length - 1;
        int ceil = Integer.MAX_VALUE;
        int floor = Integer.MIN_VALUE;

        // Time Complexity: O(log n)
        // - Binary search cuts the search space in half each time.
        //
        // Space Complexity: O(1)
        // - Only a few variables used regardless of input size.

        while (low <= high) {
            int mid = low + (high - low) / 2; // O(1)
            if (arr[mid] > n) {
                high = mid - 1;
                ceil = arr[mid];      // potential ceil found
            } else if (arr[mid] < n) {
                low = mid + 1;
                floor = arr[mid];     // potential floor found
            } else {
                ceil = arr[mid];      // exact match
                floor = arr[mid];
                break;
            }
        }

        System.out.println(floor);
        System.out.println(ceil);
    }
}

📊 Time & Space Complexity Table

Case
Time Complexity
Space Complexity
Explanation
Best
O(1)
O(1)
If n is found at the first mid point
Average
O(log n)
O(1)
Binary search divides the array in half each iteration
Worst
O(log n)
O(1)
In worst case, full binary search needed without finding n exactly