[sword finger offer] sword finger offer 53 - ii Missing numbers from 0 to n-1

The finger of the sword Offer 53 - II. 0～n-1 Missing numbers in

subject

A length of n-1 All numbers in the incremental sort array of are unique , And every number is in the range 0～n-1 within . In scope 0～n-1 Internal n There are and only one number is not in the array , Please find out the number .

Ideas

  Use binary search , If the value of the intermediate element is equal to the subscript , Then the next round of search only needs to find the right half ; If the value and subscript of the intermediate element don't want to wait , And the preceding element is equal to its subscript , This means that the middle number is exactly the first value and the element whose subscript doesn't want to wait , Its subscript is a number that does not exist in the array ; If the value of the intermediate element and the subscript are not equal , And the element before it is not equal to its subscript , That means that in the next round of search, we only need to search in the left half .

Code

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int left = 0;
        int right = nums.size() - 1;

        while(left <= right)
        {
    
            int mid = (left + right) / 2;

            //  If equal   explain   Unequal elements on the right 
            if(nums[mid] == mid)
            {
    
                left  = mid + 1;//  Look to the right 
            }
            else
            {
    
                right = mid - 1;//  It's not equal   Indicates that unequal elements are on the left 
            }
        
        }

        return left;
    }
};