思路

利用y总给的二分代码模板。
y总模板的使用技巧是：使用某种判断条件将数组分为左右两个子数组，若右子数组是满足条件的，用模板1进行二分知道找出右子数组的最左侧的点；若左子数组是满足条件的，用模板2进行二分找出左子数组最右侧的点。

C++ 代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int len = nums.size();
        if(len == 0)return -1;
        /*将数组分为左右两个数组，左子数组下标和值对应，右子数组下标和值
        不对应，利用二分法的模板2，求出满足左子数组的最右侧端点，该端点的索引+1
        即为缺失的数字
        */
        if(nums[0] != 0)return 0;//边界特判，左子数组长度等于0的情况
        int l = 0, r = len - 1;
        while(l < r){
            int mid = l + (r - l) / 2 + 1;
            if(nums[mid] == mid)l = mid;
            else r = mid - 1;
        }
        return l + 1;
    }
};