Search code examples
pythonalgorithmdata-structuresbinary-search

Ceiling of the element in sorted array

Hi I am doing DSA problems and found a problem called as ceiling of the element in sorted array. In this problem there is a sorted array and if the target element is present in the sorted array return the target. If the target element is not found in the sorted array we need to return the smallest element which is greater than target. I have written the code and also done some test cases but need to check if everything works correctly. This problem is not there on leetcode where I could run it with many different cases. Need suggestion/feedback if the problem is solved in the correct way and if it would give correct results in all cases

class Solution:
    #My approch
    def smallestNumberGreaterThanTarget(self, nums, target):
        start = 0
        end = len(nums)-1

        if target > nums[end]:
            return -1
        while start <= end:
            mid = start + (end-start)//2

            if nums[mid] == target:
                return nums[mid]
            elif nums[mid] < target:
                if nums[mid+1] >= target:
                    return nums[mid+1]
                start = mid + 1
            else:
                end = mid-1

        return nums[start]
Solution

  • IMO, the problem can be solved in a simpler way, with only one test inside the main loop. The figure below shows a partition of the real line, in subsets associated to the values in the array.

    enter image description here

    First, we notice that for all values above the largest, there is no corresponding element, and we will handle this case separately.

    Now we have exactly N subsets left, and we can find the right one by a dichotomic search among these subsets.

    if target > nums[len(nums)-1]:
    return None

s, e= 0, len(nums);
while e > s:
    m= e + ((s - e) >> 1);
    if target > nums[m]:
        s= m+1
    else:
        e= m
return s

    We can formally prove the algorithm using the invariant nums[s-1] < target <= nums[e], with the fictional convention nums[-1] = -∞. In the end, we have the bracketing nums[s-1] < target <= nums[s].