问题描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例1:
输入：[0,1,3]
输出：2
示例2：
输入：[0,1,2,4]
输出：3
解决方案
左边界i=0，右边界j=len(nums)-1；闭区间[i,j]。当i≤j时开始循环（即当闭区间[i,j]为空时跳出循环；计算中点m=(i+j)//2，其中"//"为向下取整除法；若nums[m]=m，则“右子数组的首位元素”一定在闭区间[m+1,j]中，便执行i=m+1；若nums[m]=m，则“左子数组末位元素”一定在闭区间[i,m−1]中，因此执行j=m−1；跳出时，变量i和j分别指“右子数组的首位元素”“左子数组的末位元素”，返回i。
代码清单 1 找0~n-1中缺失的数的代码清单
class Solution: def missingNumber(self, nums: List[int]) -> int: i, j = 0, len(nums) - 1 while i <= j: m = (i + j) // 2 if nums[m] == m: i = m + 1 else: j = m - 1 return i |
运行代码
结语
首先看到此题，想到的第一种方法便是二分法，当然，此题也有一些其他的办法，只是二分法更加常用，更容易想到，可以根据规则将数组划分为左子数组和右子数组两部分，根据缺失的数字为右子数组的首位元素作为对应的索引，便可得到所缺失的数。
