[sword finger offer] interview question 53- Ⅱ: missing numbers in 0 ~ n-1 - binary search

Method 1 ： Dichotomy search

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

        while( left <= right )
        {
    
            int mid = left + ( right - left ) / 2;
            if( nums[mid] == mid )
            {
    
                left = mid + 1;
            }
            else
            {
    
                right = mid - 1;
            }
        }
        return left;

    }

};

Method 2 ： Exclusive or

0-n-1 Number , And 0-n XOR can get the final result

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int flag = 0;
        for( int i = 0; i < nums.size(); i++ )
        {
    
            flag ^= nums[i];
        }
        for( int i = 0; i <= nums.size(); i++)
        {
    
            flag ^= i;
        }
        return flag;
    }
};

Method 3 ：0-n Add subtract the number in the array