剑指Offer53II.0～n1中缺失的数字（二分检索）

难度：简单

一个长度为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

解题思路：
当排序好的数组进行检索时，一般采用二分检索。
每次取中值




n


u


m


s


[


m


i


d


]



nums[mid]


nums[mid]时，判断该中值是否与对应的索引相等，即，




n


u


m


s


[


m


i


d


]


=


=


m


i


d



nums[mid]==mid


nums[mid]==mid，如果相等，左边界索引等于




m


i


d


+


1



mid+1


mid+1；如果不相等，右边索引等于




m


i


d


−


1



mid-1


mid−1。
循环退出的条件是当左边界索引大于右边界索引时，退出检索，返回左边界索引。

python代码：

# 二分检索
class Solution:
def missingNumber(self, nums: List[int]) -> int:
i, j = 0, len(nums)-1
while i <= j:
mid = (i+j) // 2
if nums[mid] == mid:
i = mid+1
else:
j = mid-1
return i


复杂度分析：

• 时间复杂度
  
  
  
  
  O
  
  
  (
  
  
  l
  
  
  o
  
  
  g
  
  
  N
  
  
  )
  
  
  
  O(logN)
  
  
  O(logN)：每次缩小一倍，为对数级别的复杂度；
• 空间复杂度
  
  
  
  
  O
  
  
  (
  
  
  1
  
  
  )
  
  
  
  O(1)
  
  
  O(1)：常数大小的额外空间。