求0～n-1中缺失的数字

问题简述

数组 [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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 在该数字之前，有 nums[i] == i，之后有 nums[i] != i，根据该性质可以使用二分查找；

• 跳出循环时，变量 l 和 r 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素”，即 l == r + 1，缺失的元素正是 l

Python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:

        l, r = 0, len(nums) - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == m:
                l = m + 1
            else:
                r = m - 1
        
        return l