【二分查找】0～n-1中缺失的数字

0～n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字

​ 一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

解题思路

​ 这道题还是很好找数组的二段性的，假设有一个数组，n = 9，如下图所示：

此时划分为了两个区间，那么就有两种情况：

1. 如果 mid 落在完整区间内，即 mid == nums[mid]，此时说明缺失元素不在该区间，则舍去 [left, mid] 区间的元素，直接 left = mid + 1 即可！
2. 如果 mid 落在缺失区间内，即 mid != nums[mid]，此时我们不然直接让 right = mid - 1，因为有可能 mid 就是缺失区间的左端点，所以我们只能让 right = mid。

​ 从上面的分析看来，其实就是一个求区间左端点的二分题！

​ 但是这里有个细节问题，就是返回值，假设此时数组只有两个元素 0 和 1，可以得到缺失的元素是 2，此时是需要我们特判一下的，因为缺失元素不存在这个数组内，并且这个缺失元素还是大于数组中其它元素的，此时一直都是 nums[mid] == mid，最后 left 不断移动，就和 right 相遇就结束了，但是因为我们终止循环条件的原因，它不会超过 right，就会导致 left 是没办法得到这个缺失元素 2。

​ 所以我们需要判断一下，如果最后 nums[left] == left 的话，说明缺失元素不在数组中，此时我们要返回的就是 left + 1，反之则返回 left 即可！

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(mid == nums[mid])
                left = mid + 1;
            else
                right = mid;
        }
        return left == nums[left] ? left + 1 : left;
    }
};