难度: Easy
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5] 输出: 4
示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7
提示：
1 <= records.length <= 10000
Submission
运行时间: 44 ms
内存: 15.8 MB
class Solution:
def missingNumber(self, nums: List[int]) -> int:
lo = 0
hi = len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == mid:
lo += 1
else:
hi = mid - 1
return lo
Explain
题解采用了二分查找的方法来寻找缺失的学号。由于数组是升序的，如果没有缺失，每个元素的值应该等于其索引。算法利用这一点，对数组进行二分查找。当中间元素的值等于其索引时，意味着缺失的学号在右侧，因此调整左边界；如果不等，说明缺失的学号在左侧或就是当前的中间位置，因此调整右边界。最终，左边界 'lo' 将停在缺失学号的位置。
时间复杂度: O(log n)
空间复杂度: O(1)
# 定义解决方案类
class Solution:
def missingNumber(self, nums: List[int]) -> int:
# 初始化左右边界
lo = 0
hi = len(nums) - 1
# 当左边界不大于右边界时循环
while lo <= hi:
# 计算中点
mid = (lo + hi) // 2
# 检查中点的值是否与其索引相等
if nums[mid] == mid:
# 如果相等，缺失的数字在右侧
lo += 1
else:
# 如果不等，缺失的数字在左侧或就是当前mid
hi = mid - 1
# 当循环结束时，lo 指向缺失的数字
return lo
Explore
当nums[mid]等于mid时，表示从索引0到mid的元素都恰好等于其索引值，说明这部分数组是完整的，没有缺失。因此，如果存在缺失的学号，它必须位于mid索引之后的数组部分。
如果nums[mid]不等于mid，说明在mid之前至少有一个数字是缺失的，因为理论上在没有缺失的情况下，每个元素应与其索引相等。这种不匹配可能是因为前面有缺失的数字导致后面的数字前移，所以缺失的学号可能就是mid本身或者在mid之前。
算法通过调整lo和hi的值来缩小搜索范围，最终lo将停在第一个使得nums[lo]不等于lo的位置，这个位置就是缺失数字的位置。如果数组是完整的，则lo会停在nums长度的位置，也就是最后一个数字的下一个位置。
是的，如果数组中没有缺失的学号，那么每个元素的索引都将与其值相等。在这种情况下，lo会逐步增加直到超过数组的最高索引，最后lo将等于nums的长度，也就是第一个不存在的索引，这也符合预期的结果。