1060. Missing Element in Sorted Array (Array, Binary Search)

링크 - https://leetcode.com/problems/missing-element-in-sorted-array/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 Binary Search로 풀 수 있다. 주의해야 할 점은 mid를 right - (right - left) // 2로 해서 풀어야 한다는 점이다. 그래야 항상 left와 비교가 가능하다.

Code

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = right - (right - left) // 2
            missing_numbers = (nums[mid] - nums[left]) - (mid - left)

            if missing_numbers < k:
                k -= missing_numbers
                left = mid
            else:
                right = mid - 1

        return nums[left] + k

Complexity

Time Complexity: O(log N)

Space Complexity: O(1)