跟着姚桑学算法-0到n-1中缺失的数字

题. 0到n-1中缺失的数字

一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。

在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

数据范围
1≤n≤1000

样例

输入：[0,1,2,4]

输出：3

【题解】--- 二分法

这道题目给定的是递增数组，假设数组中第一个缺失的数是 x，那么数组中的数如下所示；


从中可以看出，数组左边蓝色部分都满足 nums[i] == i ，

数组右边x-1后的部分都不满足 nums[i] == i，因此我们可以二分出分界点 x 的值。

另外要注意特殊情况：当所有数都满足nums[i] == i 时，表示缺失的是 n。

复杂度分析：

二分中的迭代只会执行 O(logn) 次，因此时间复杂度是 O(logn)。

C++代码实现：

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[r] == r) r ++ ;
        return r;
    }
};