0~n-1中缺失的数字

关键词：二分法

题目描述

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

示例 1：

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

示例 2：

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

解法

解法一：

思路：

排序数组中的搜索问题，首先想到 二分法 解决。
根据数据和对应的下标进行判断。

算法流程：

排除第一个和最后一个元素的影响；
找第一个数值不等于下标的数字。

代码：

int missingNumber(vector<int> &nums)
{
    int size = nums.size();
    if(size <= 0 || nums[0] != 0) return 0;
    if(nums[size - 1] != size) return size;
    int l = 0, r = size - 1, m = 0;
    while (l < r - 1)
    {
        m = (l + r) / 2;
        if(nums[m] == m) l = m;
        else r = m;
    }
    return l + 1;  
}

知识点

二分法