题解 | #缺失数字#

二分查找

首先要知道什么情况下可以使用二分

如果能够明确二分之后，答案存在于二分的某一侧，就可以使用二分。
这里强调：单调一定可以使用二分，而二分不一定需要单调
本题刚好答案存在于二分的某一侧。

二分的步骤：

1. 找中间值 mid = (l+r+1)/2
2. if(check(mid)) check是找到答案所在的一侧
3. 更新l或者r

那么如何找到答案所在的一侧呢？
注意到本题的下标就是值
所以我们取中间值 mid，接着加上与最右边的值r的距离，然后与r 相比较

• 如果nums[mid] + r - mid == a[r]，那么说明答案在左侧，即缺失的数在左侧
• 如果nums[mid] + r - mid != a[r]，那么说明答案在右侧，即缺失的数在右侧

如何理解呢？
我们来看看样例1
[0,1,2,3,4,5,7]

1. 首先取中间值mid = 3
2. 然后加上距离 3 + r - l = 3 + 6 - 3 = 6 != 7 说明答案在右侧
3. 更新l = mid + 1;

因为数组的值是严格从0~n递增的，所以如果mid 加上距离r不等于a[r]，说明有数缺失

class Solution {
public:
    int solve(vector<int>& a) {
        // write code here
        int l = 0 , r = a.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[mid] + r - mid == a[r]) r = mid;
            else l = mid + 1;
        }
        if(a[l] == l) return a.size();
        return l;
    }
};