1060. Missing Element in Sorted Array

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

排好序的数组找在[nums[0], +inf)中第K个丢失的数。如果不丢失，第i个数的值应该是nums[0] + i。基于此二分，nums[mid] - nums[start] - (start - mid)为nums[start]到nums[mid]丢失的数的个数，小于k时start = mid并让k减去这部分cover的missing num。start最后停在end前并且missing number没到k的位置。二分考虑的是丢失的在nums[N-1]内的情况，当超过N-1时直接让nums[N-1]加上缺失数目。

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        const int N = nums.size();
        int missingNum = nums[N - 1] - nums[0] + 1 - N;
        if (missingNum < k) return nums[N - 1] + k - missingNum;
        int start = 0, end = N - 1;
        while (start < end - 1) {
            int mid = start + (end - start) / 2;
            int missing = nums[mid] - nums[start] - (mid - start);
            if (missing < k) {
                start = mid;
                k -= missing;
            } else end = mid;
        }
        return nums[start] + k;
    }
};