【二分查找】1539. 第 k 个缺失的正整数

**二分查找**

二分查找是一种常见的算法，用于在一个有序列表中找到一个特定的元素。它通过将列表分成两半，并根据所需元素的位置来决定下一步的操作。

**第 k 个缺失的正整数**

假设我们有一个从1 到 n 的连续正整数集合，其中一些数字丢失了。我们的任务是找到第 k 个丢失的正整数。

**算法思路**

我们可以使用二分查找来解决这个问题。具体来说，我们可以将集合分成两半，并根据 k 的值决定下一步的操作。

1. 如果 k 小于或等于集合的一半，我们知道第 k 个丢失的数字一定在左半部分。
2. 否则，我们知道第 k 个丢失的数字一定在右半部分。

我们可以重复这个过程，直到找到第 k 个丢失的数字。

**代码示例**

def findKthMissingPositiveNumber(arr, k):
 """
 Find the kth missing positive integer in a sorted array.

 Args:
 arr (list): A sorted list of integers.
 k (int): The index of the missing positive integer to find.

 Returns:
 int: The kth missing positive integer.
 """
 left, right =0, len(arr) -1 while left <= right:
 mid = (left + right) //2 # If there are at least k numbers in the left half,
 # then the kth number must be in the left half.
 if arr[mid] - left < k:
 left = mid +1 else:
 right = mid -1 return left + k# Example usage:
arr = [1,2,3,4,6,7,8,10]
k =3print(findKthMissingPositiveNumber(arr, k)) # Output:5