1060. Missing Element in Sorted Array

bisection O(logn) time O(1) space
在数组中找missing number的『下界』，找下界的好处是最后确定缺哪个数直接计算即可，比找上界省事

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = size(nums), l = 0, r = n - 1;
        while (l < r) {
            int m = (l + 1 + r) / 2; // 找下界为了避免死循环要+1
            if (nums[m] - nums[0] - m < k) { // (nums[m] - nums[0]) - (m - 0)得到nums[0]和nums[m]中间缺了几个数，如果少于k个说明nums[m]可能是下界
                l = m;
            } else {
                r = m - 1;
            }
        }
        return nums[0] + l + k; // 从nums[0]开始出现了l个数缺k个数，即nums[l] + k - (nums[l] - nums[0] - l)，从nums[l]开始数第k - (nums[l] - nums[0] - l)个数
    }
};

二分遍历整个数组，找出missing element在数组中的上界
对于一个数nums[m]，如果nums[m] - nums[0] - m >= k，则所求的missing element小于nums[m]，nums[m]是一个备选上界，否则肯定大于nums[m]并且nums[m]一定不是一个上界
找到上界nums[l]以后，分情况讨论

1. 如果nums[l]是一个真上界，则missing element在(nums[l - 1], nums[l])之间，即k - (nums[l - 1] - nums[0] - (l - 1)) = k + nums[0] + l - 1，即从nums[0]开始跳过数组内的l - 1个数后找出第k个缺失的数
2. 如果nums[l]是一个假上界，即数组里所有数都要比所求的missing element小，则应为k - (nums[l] - nums[0] - l) = k + nums[0] + l，即从nums[0]开始跳过数组内的l个数后找出第k个缺失的数

综合起来为k + nums[0] + l - isValid(nums, l, k)

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size(), l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isValid(nums, m, k)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[0] + k + l - isValid(nums, l, k);
    }

    bool isValid(const vector<int> &nums, int m, int k) {
        return nums[m] - nums[0] - m >= k; // 说明nums[m]比较大，第k个missing的数可以在nums[m]之内，即nums[0], ..., nums[0] + m, ..., nums[m]，所以nums[m] - (nums[0] + m) >= k
    }

};