题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
样例
输入：[0,1,2,4]
输出：3

解法：二分

假设数组中第一个缺失的数是 xx，那么数组中的数如下所示；

从中可以看出，数组左边蓝色部分都满足nums[i] == i，数组右边橙色部分都不满足nums[i] == i，因此我们可以二分出分界点 x 的值。
另外要注意特殊情况：当所有数都满足nums[i] == i时，表示缺失的是 nn。
时间复杂度O(logn)，空间复杂度O(1)

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty()) return 0;
        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 (nums[l] == l) l++;
        return l;
    }
};