剑指Offer53-II-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）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用二分法，如果发现数字位置与数字不一致，说明该数字不符合要求：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
if len(nums) == 1 and nums[0] == 0: return 1
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l)//2
if nums[mid] != mid :
r = mid - 1
else:
l = mid + 1
return l if nums[l] != l else l + 1
二解
与一解思路相同，另循环代码退出条件为l <= r，考虑特殊情况： [0,1,2,3]
考虑特殊情况 [0]：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l)//2
if nums[mid] != mid :
r = mid - 1
else:
l = mid + 1
return l