剑指Offer[53-2]-0～n-1中缺失的数字

题目

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

示例：

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

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

python代码

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i]!=i:
                return i
        return len(nums)

上述解法非常常规，根据题意，数组中的每个值应该等于它的索引值，所以直接遍历整个数组，当发现值不等于索引值时，就说明遇到了缺失值，另外要注意：当遍历结束后，仍没有找到缺失值，则说明缺失值为n。

优化

其实优化的方法也很直接，因为数组为有序数组，且题目涉及到找值，一般情况下都可以使用二分查找法，只不过我们这里的目标值变成了当前值的索引值。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left=0
        right=len(nums)-1
        if nums[-1]==len(nums)-1:
            return len(nums)
        while left<=right:
            mid = (left+right)//2
            if nums[mid]==mid:
                left = mid+1
            else:
                right = mid-1
        return left