Problem

Given a sorted array and a value x, the ceiling of x in sorted array. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x.

Definition

the ceiling of x is the smallest element in array greater than or equal to x.

Examples

Example 1:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 5
 Output: 6
 Explanation: The smallest element greater than or equal to 5 is 6.

Example 2:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 11
 Output: 12
 Explanation: The smallest element greater than or equal to 11 is 12.

Example 3:

1
2
3

 Input: arr = [1, 2, 4, 6, 10, 12, 14], x = 15
 Output: -1
 Explanation: There is no element greater than or equal to 15.

Variant

Find smallest letter greater than target in a sorted array of letters

Solution

Method 1 - Binary Search

O(lgn) solution using modified Binary Search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public static int findCeiling(int[] arr, int x) {
	    int start = 0, end = arr.length - 1;
	    int ceiling = -1;
	
	    while (start <= end) {
	        int mid = (start + end) / 2;
	        // a[mid] is the ceiling
	        if (arr[mid] == x) {
	            return arr[mid];
	        } else if (arr[mid] < x) {
	            start = mid + 1;
	        } else {
		        // a[mid] is the smallest element found so far that is greater than x. So it is a candidate for the ceiling of x
	            ceiling = arr[mid];
	            end = mid - 1;
	        }
	    }
	
	    return ceiling;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def find_ceiling(arr, x):
    start, end = 0, len(arr) - 1
    ceiling = -1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid]
        elif arr[mid] < x:
            start = mid + 1
        else:
            ceiling = arr[mid]
            end = mid - 1

    return ceiling

Complexity

  • ⏰ Time complexity: O(log n), due to binary search.
  • 🧺 Space complexity: O(1), as no extra space is used apart from a few variables.