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

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

题目

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

思路

  使用二分查找，如果中间元素的值和下标相等，那么下一轮的查找只需要查找右半边；如果中间元素的值和下标不想等，并且前面一个元素和他的下标相等，这就意味着中间的数字正好是第一个值和下标不想等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面的元素和他的下标不相等，那就意味着下一轮查找我们只需要在左半边查找即可。

代码

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

        while(left <= right)
        {
    
            int mid = (left + right) / 2;

            // 如果相等 说明 不相等的元素在右边
            if(nums[mid] == mid)
            {
    
                left  = mid + 1;// 往右边查找
            }
            else
            {
    
                right = mid - 1;// 不相等 说明不相等的元素在左边
            }
        
        }

        return left;
    }
};