Python递归二分查找问题：如何获取列表中≥目标值的首个索引？

任务要求 #

• 给定有序列表，找到目标值及其两倍值对应的首个大于等于该值的索引
• 输入规则：
  • 第一行：列表长度
  • 第二行：有序列表元素
  • 第三行：目标值
• 输出：两个索引，若不存在符合条件的元素则返回-1

示例 #

输入 #

6
1 2 4 4 6 8
3

预期输出 #

3 5

现有问题 #

当前实现的递归二分查找无法正确定位首个大于等于目标值的索引，运行示例输入得到输出3 4，不符合预期。现有代码如下：

def binarySearch(arr, x, left, right):
    if right <= left:
        return -1
    mid = (left + right) // 2
    if arr[mid] >= x: 
        return mid
    elif x < arr[mid]:          
        return binarySearch(arr, x, left, mid)
    else: 
        return binarySearch(arr, x, mid + 1, right)

def main():
    n = int(input())
    k = input().split()
    q = []
    for i in k:
        q.append(int(i))
    s = int(input())
    res1 = binarySearch(q, s, q[0], (n-1))
    res2 = binarySearch(q, (s*2), q[0], (n-1))
    print(res1, res2)

if __name__ == "__main__":
    main()

问题分析与修正 #

1. 递归逻辑错误：原代码找到arr[mid] >= x时直接返回mid，但这不一定是第一个满足条件的索引，需继续向左搜索更早的符合条件位置。
2. 初始参数错误：调用binarySearch时传入的left是列表第一个元素的值，而非索引0，导致搜索范围完全错误。

修正后的代码 #

def binarySearch(arr, x, left, right):
    # 搜索范围耗尽时，left即为首个大于等于x的位置（若存在）
    if left > right:
        return left if left < len(arr) else -1
    mid = (left + right) // 2
    if arr[mid] >= x:
        # 找到符合条件的元素，继续向左寻找更早的索引
        return binarySearch(arr, x, left, mid - 1)
    else:
        # 当前元素小于目标值，向右搜索
        return binarySearch(arr, x, mid + 1, right)

def main():
    n = int(input())
    q = list(map(int, input().split()))
    s = int(input())
    # 初始搜索范围为索引0到n-1
    res1 = binarySearch(q, s, 0, n-1)
    res1 = res1 if res1 != len(q) else -1
    res2 = binarySearch(q, s*2, 0, n-1)
    res2 = res2 if res2 != len(q) else -1
    print(res1, res2)

if __name__ == "__main__":
    main()

代码说明 #

• 递归逻辑修正：当arr[mid] >= x时，不直接返回mid，而是继续在左半区间（left到mid-1）搜索，确保找到第一个满足条件的索引。
• 初始参数修正：调用时传入left=0（起始索引），保证搜索范围正确。
• 边界处理：当搜索范围耗尽（left > right），left就是首个大于等于x的元素位置；若left等于列表长度，说明所有元素都小于x，返回-1。

测试示例输入，将得到预期输出3 5。

内容的提问来源于stack exchange，提问作者r3tr0