53 - II. 0～n-1中缺失的数字

思路：二分

如果nums[m]==m，则”右区间的首位“一定在[m+1,j]，执行i=m+1;

如果nums[m]!=m，则”左区间的末位“一定在[i,m-1], 执行j=m-1;

class Solution {
public:
    int missingNumber(vector& nums) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+right>>1;
            if(nums[mid]==mid)left=mid+1;
            else right=mid-1;
        }
        return left;
    }
};

时间复杂度 O(log n)

空间复杂度 O(1)