1060. Missing Element in Sorted Array

link

dataset 5 * 10 ^ 4

Method 1

Linear O(n)

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:

        n = len(nums)

        left = nums[0]

        for i in range(n):
            while left < nums[i]:
                k -= 1
                if k == 0:
                    return left
                left += 1

            left += 1

        # need to -1 if it comes here, couse if it +1 when leave the loop last time
        return left - 1 + k 

Method 2

Binary Search

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:

        n = len(nums)

        l, r = nums[0], nums[-1] + k

        def check(num):
            idx = bisect.bisect_left(nums, num)

            missing = num - nums[0] - idx

            if idx == n or num != nums[idx]:
                missing += 1
        
            if missing >= k:
                return True

            return False

        while l < r:
            mid = l + (r-l) // 2
            if check(mid):
                r = mid
            else:
                l = mid + 1
        
        return l