1060. Missing Element in Sorted Array.md

1060. Missing Element in Sorted Array

https://leetcode.com/problems/missing-element-in-sorted-array/

It should be easy to come up with the idea of binary search but may be challenging to reason the correctness of an implementation. Let lo and hi be the starting and end indicies indicating the range for binary search.

Property: the total count of missing numbers between lo and hi is (nums[hi] - nums[lo]) - (hi - lo).

• Explain: nums[hi] - nums[lo] + 1 is the total count of numbers in the range [lo .. hi] and hi - lo + 1 is the count of numbers existing in that range.
• Example: Given nums = [3, 5, 7], lo = 0 and hi = 2. Count of missing numbers in this range is 7 - 3 - (2 - 0) = 2, which is 4 and 6.

By appending inf to the end of the array, we can maintain an invariant through out binary search: missing number n must be in the range between lo and hi. i.e. nums[lo] < n < nums[hi]

1. Base case: initially, nums[hi] = inf so the invariant holds.
2. Inductive step: let mid = (lo + hi) // 2 and the count of missing numbers in the range [lo .. mid] be m, which is (nums[mid] - nums[lo]) - (mid - lo) according to the property above. We will update lo, hi and k on each step of binary search.
   1. if m >= k, n must be the kth missing number in the range [lo .. mid];
   2. Otherwise, n must be the k - mth missing number in the range [mid .. hi]. (update with k' = k - m)
3. Termination condition: when lo = hi - 1, the search terminates and n will be the k-th number after nums[lo].

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        nums.append(inf)
        lo = 0
        hi = len(nums) - 1
        while lo < hi - 1:
            mid = (lo + hi) // 2
            missing = nums[mid] - nums[lo] - (mid - lo)
            if missing >= k:
                hi = mid
            else:
                lo = mid
                k -= missing
        return nums[lo] + k