Find the Ceiling of an Element in a Sorted Array - Java Solution

1. Introduction

In this blog post, we will discuss how to find the ceiling of a given number in a sorted array. The ceiling of a number x is the smallest element in the array greater than or equal to x. This problem is a variation of binary search.

Problem

Given a sorted array and a value x, find the ceiling of x in the array. If the ceiling doesn’t exist, output -1.

Example 1:

Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 0

Output: 1

Example 2:

Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 1

Output: 1

Example 3:

Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 5

Output: 9

Example 4:

Input: a[] = {1, 3, 9, 15, 15, 18, 21}, x = 25

Output: -1

2. Solution Steps

1. Use binary search to find the ceiling.

2. If the current element is greater than or equal to x, check if it’s the ceiling.

3. Continue the search in the left sub-array if the current element is greater than x.

4. Continue the search in the right sub-array if the current element is less than x.

5. If x is greater than all elements, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a = {1, 3, 9, 15, 15, 18, 21};
        System.out.println("Ceiling of 0: " + findCeiling(a, 0));
        System.out.println("Ceiling of 1: " + findCeiling(a, 1));
        System.out.println("Ceiling of 5: " + findCeiling(a, 5));
        System.out.println("Ceiling of 25: " + findCeiling(a, 25));
    }

    // Method to find the ceiling in a sorted array
    public static int findCeiling(int[] a, int x) {
        int start = 0, end = a.length - 1;
        int res = -1;

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

            if (a[mid] == x) return a[mid];

            if (a[mid] < x) {
                start = mid + 1;
            } else {
                res = a[mid];
                end = mid - 1;
            }
        }
        return res;
    }
}

Output:

Ceiling of 0: 1
Ceiling of 1: 1
Ceiling of 5: 9
Ceiling of 25: -1

Explanation:

The findCeiling method performs a binary search to find the ceiling of x. 

For the input array [1, 3, 9, 15, 15, 18, 21], it finds the smallest element greater than or equal to x. 

For x = 0, 1 is the ceiling; for x = 1, the ceiling is still 1; for x = 5, the ceiling is 9; and for x = 25, there is no ceiling (hence -1).