1060. 有序数组中的缺失元素

给出一个有序数组 A，数组中的每个数字都是 独一无二的，找出从数组最左边开始的第 K 个缺失数字。
示例 1：

输入：A = [4,7,9,10], K = 1
输出：5
解释：
第一个缺失数字为 5 。

  思路：
1. 这题明显是可以遍历做完的。但是对于有序数组，遍历O(N)解法往往不够，优先考虑二分查找。
2. 注意一点，从数组最左边开始到索引i之间缺少的数字数目可以用：nums[i] - nums[0] - i表示。
3. 那么，可以在二分时判断第mid索引缺少与k比较。找到最左边缺少数目=k的索引。代码如下：

class Solution {
    public int missingElement(int[] nums, int k) {
        // 0  2  1 0
        int left = 0;
        int right = nums.length;
        int idx = nums[nums.length-1] - nums[0] - nums.length + 1;
        if(k>idx){
            return nums[right-1]+(k-idx);
        }
        while(left<right){
            int mid = (left+right)/2;
            idx = nums[mid] - nums[0] - mid;
            if(idx>k){
                right = mid;
            }else if(idx<k){
                left = mid+1;
            }else{// 相当于是等于的时候，需要找到最左边的节点值;
                right = mid;
            }
        }
        return nums[left-1] + k-(nums[left-1] - nums[0] - (left-1));
    }
}