难度：简单

一个长度为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

解题思路：
当排序好的数组进行检索时，一般采用二分检索。
每次取中值 n u m s [ m i d ] nums[mid] nums[mid]时，判断该中值是否与对应的索引相等，即， n u m s [ m i d ] = = m i d nums[mid]==mid nums[mid]==mid，如果相等，左边界索引等于 m i d + 1 mid+1 mid+1；如果不相等，右边索引等于 m i d − 1 mid-1 mid−1。
循环退出的条件是当左边界索引大于右边界索引时，退出检索，返回左边界索引。

python代码：

# 二分检索
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums)-1
        while i <= j:
            mid = (i+j) // 2
            if nums[mid] == mid:
                i = mid+1
            else:
                j = mid-1
        return i

复杂度分析：

• 时间复杂度 O ( l o g N ) O(logN) O(logN)：每次缩小一倍，为对数级别的复杂度；
• 空间复杂度 O ( 1 ) O(1) O(1)：常数大小的额外空间。