题解 | #缺失数字#

题目应该是默认数组有序的，用二分搜索即可，O(logn). 其他方法如位运算或者求和公式都是O(n)的复杂度。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 找缺失数字
# @param a int整型一维数组 给定的数字串
# @return int整型
#
class Solution:
    def solve(self , a ):
        # write code here
        n = len(a)
        lo, hi = 0, n-1
        pos = 0
        while lo <= hi:
            mid = lo + (hi-lo)/2
            if a[mid] == mid:
                lo += 1
            elif a[mid] > mid:
                hi -= 1
            pos = mid
        if a[pos] == pos:
            return pos +1
        elif a[pos] > pos:
            return pos
        return pos