Ceiling(Upper Bound)

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array

Question

Math

Ceil is the upper limit of a decimal number. In this problem, since we are dealing with integers, we will consider the element after the target element, or the target element itself if it is present in the array as the upper limit or ceil.

Intuition

1. We are looking for the smallest element after the target element, also if the target element exists that simply our ceiling.
2. We can do it in linear search, scan all the elements starting from index 0, and return the first one that is the target or greater than.

Here's the Python code for finding the ceiling element by linear search: Time complexity O(n)

Copy

def ceiling(arr, target):
    for i in range(len(arr)):
        if arr[i] >= target:
            return arr[i]
    return -1

3. But since the array is sorted, we can solve this in logarithmic time? We will need to make a binary decision. What is that binary decision that will help us more closer to the target ?
4. We can divide the array into two halves: the upper half, where all values are greater than the target, and the lower half, where all values are less than the target. When we are in the upper half, we might be on the target or it will be to the left, so we discard all elements to the right. Conversely, when in the lower half, the target will be to the right, so we discard all elements to the left.
5. If the target exists we will include it in the upper half.
6. We hop between each half chopping elements and reducing the range, the last element that is cut from the upper half will be either the target or the smallest value greater than it. We keep track of the most up-to-date value and return it.

1. Target exists in the array.

If the target value is present in the array, the upper bound or ceiling will be equal to the target value. As an example, in the array [1, 2, 5, 10, 10, 12, 19], if the target value is 5, the ceiling or upper bound will be 5.


7. The problem is reduced to finding the 🔑Find the First True in a Sorted Boolean Array .

class Solution:

    def firstTrue(self, bools):

        (left, right) = (0, len(bools) - 1)
        possibleValue = -1

        while left <= right:

            mid = left + (right - left) // 2
						
					# True
            if bools[mid]: 
                possibleValue = mid
                right = mid - 1
						
					# False
            else:
                left = mid + 1

        return possibleValue

class Solution:

    def ceil(self,nums,target):

        left, right = 0, len(nums) - 1
        ceil = -1

        while left <= right:

            mid = left + (right - left) // 2
						
            #True
                # Possible Value
            if nums[mid] >= target:
                ceil = mid
                right = mid - 1
						
						# False
            else: # target > nums[mid]
                left = mid + 1

				# if not found will return -1  
        return ceil

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition