二分查找 python

因为缺失了 一个数字 所以 下标指向数组的值 一定是 大于或者等于 当前 下标的
所有采用 二分的方法 逐个的去逼近 缺失的值
无非就是两种情况
第一种：下标指向的值 等于 当前的下标，那么 缺失的肯定是在当前下标的右侧，所以left=mid+1
第二钟：下标指向的值 大于 当前的下标，那么 缺失的肯定是在mid的左侧，所以right=mid
最后逼近到 left = mid + 1的时候 mid的左侧都是不确实的，mid+1就正好是缺失的值
并且此时 left == right 所以跳出循环 返回正确的答案

class Solution:
    def solve(self , a ):
        n = len(a)
        if n == 0: return 0
        # border condition
        if a[0] != 0: return 0
        if a[-1] + 1 == n: return n
        # mid condition
        left, right = 0, n - 1
        while left < right:
            mid = left + (right - left) // 2
            # 相等的情况 结果只会出现在 mid 右侧
            if a[mid] == mid:
                left = mid + 1
            # 只会出现 所在下标的取值 大于等于 当前 下标
            if a[mid] > mid:
                right = mid
        return left