一个长度为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
思路：
排序数组的查找问题，首先应该想到使用二分法；
数组索引：0 1 2 3 4 5 6 7 8
数组元素：0 1 2 3 4 5 6 7 9
可以看出，数组前一部分num[i] = i ， 后一部分num[i] != i
因此可以将数组划分为两个部分，左子数组和右子数组
初始化，左边界0，右边界len(nums)-1
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即可。
python3解法：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
length = len(nums)
i, j = 0, length - 1
while i<= j:
m = (i + j) // 2
if nums[m] == m:
i = m + 1
else:
j = m - 1
return i
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
