class Solution {
public:
    int getMissingNumber(vector<int>& nums) {

        if (nums.empty()) return 0;
        //假设左边区间都是齐的，右边区间缺了一个数，说明右边所有的元素都不满足下标和值是相等的
        int l=0;
        int r = nums.size()-1;
        while(l<r){
            int mid = l+r>>1;
            if(nums[mid]!=mid) r = mid;
            else l = mid + 1;//不等于就说明下标和值是不相等的，那么mid此时就一定在右区间内。所以就更新右区间
        }//这一步操作就可以找到那个值的下标了，而此事的下标就是对应那个值，[0,1,2,4]最后停在4，因为是找到右边区间的第一个数字，而下标正好对应失去的值（因为后面的4填充了3的位置）
        //但是还要特判一下,原因是？？？
        if(nums[r]==r)r++;//[1,2,3,5]
        return r;
    }
};