// 二分
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if(l == nums[l]) l++;

        return l;
    }
};

// 间隔法
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 第一个元素不是 0 的情况
        if(nums[0]) return 0;

        // 一般情况
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] - nums[i - 1] > 1)
            {
                return nums[i] - 1;
            }
        }

        return nums.size();
    }
};