1539. 第 k 个缺失的正整数

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # 暴力解法 时间复杂度O(n+k)
        # i = 1
        # j = 0
        # None_num = 0
        # while None_num!=k :
        #     if (j<len(arr) and i != arr[j]) or (j>=len(arr)):
        #         None_num += 1
        #     else:
        #         j += 1
        #     i += 1
        # return i-1

        # 聪明解法
        # 对于每个arr的元素，我们都可以唯一确定到第 i 个元素为止缺失的元素数量为 a_i - i - 1。
        # 确定缺失的第 k 个数为 k - p_i-1 + a_i-1
        if arr[0]>k:
            return k
        arr.append(10**4)
        left = 0
        right = len(arr)-1
        while left<=right:
            half = (left+right)//2
            p_pro = arr[half-1]-half+1-1 if half-1>=0 else -half #  前后空缺值数量。
            p_post = arr[half]-half-1
            # print(left,half,right,":",p_pro,p_post,": k=%d"%k)
            # print( "k <= p_pro ?",k <= p_pro)
            if p_pro < k and k <= p_post:
                return k - p_pro + arr[half-1]
            elif k <= p_pro:
                right = half-1
            elif p_post < k:
                left = half+1