剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution:
    # 自己写的方法，比较啰嗦一些。
    # def missingNumber(self, nums: List[int]) -> int:
    #     if nums[0] != 0:
    #         return 0
    #     else:
    #         for i in range(len(nums)):
    #             if i == len(nums)-1:
    #                 return i+1
    #             if nums[i] != nums[i+1]-1:
    #                 return i+1
    # 大佬写的代码，排序数组中的二分问题，用的是二分法解决的。
    # 二分查找的大概思路是:
    # [0 1 2 3 5]
    # start=0,end=len(list)-1
    # middle = (start+end)//2
    # 判断一下list[middle]是否等于middle
    # 如果等于,则需要找的数在 (middle+1)-end 的范围里
    # 否则,就在 0-(middle-1)的范围里.
    # 循环
    #  0 4 2
    #  3 4 3
    #  4 4 4
    def missingNumber(self, nums: List[int]) -> int:
        start, end = 0, len(nums)-1
        while start <= end: 
            middle = (start+end)//2
            if nums[middle] == middle: start += 1
            else: end -= 1
        return start