Python二分搜索运行过慢导致程序崩溃 如何优化批量列表匹配算法

直接导致程序崩溃的核心问题 #

你的代码运行卡死、VS Code崩溃完全是逻辑写错了位置，和硬件无关：

• 二分边界没有重置：low和high的初始化被放在了遍历B元素的循环外面。每处理B里的一个元素时，用的都是上一次搜索遗留的边界值，根本没有覆盖整个A数组，从根源上导致搜索逻辑失效。
• 找到匹配后死循环：当i == A[middle]时，代码只执行了matched_list.append(middle)，既没有调整low/high的值，也没有break跳出while循环，导致while low <= high的条件永远成立，进入无限循环——这就是程序跑不动的直接原因。
• 找不到元素的处理逻辑错误：代码里写的if low > high: return(-1)会在第一个搜不到的元素出现时，直接终止整个函数，返回单个-1，完全不会处理B里剩下的元素，不符合题目要求的输出规则。
• 无法保证返回首次出现的索引：就算解决了死循环问题，普通二分找到的第一个匹配位置不一定是目标值在A中最早出现的位置——如果A存在重复元素，可能会返回中间位置的匹配，而不是最左侧的首次出现索引。

修正规则 #

• 每处理B中的一个待匹配元素，都要把low和high重置为0和n-1，保证每次搜索范围覆盖完整的A数组
• 采用最左匹配二分逻辑：找到目标值的匹配位置后不立刻停止，继续向左收缩搜索范围，直到锁定最早出现的索引
• 搜索结束后校验结果：匹配到目标值就存入对应索引，没匹配到就存入-1到结果列表，不要直接终止函数

可运行的正确代码 #

def binary_search(A, B, n):
    matched_list = []
    for target in B:
        # 每次搜索前重置边界
        low, high = 0, n - 1
        # 默认结果为-1，代表找不到
        res = -1
        while low <= high:
            middle = (low + high) // 2
            if target < A[middle]:
                high = middle - 1
            elif target > A[middle]:
                low = middle + 1
            else:
                # 找到匹配，记录当前位置后继续往左找更早的匹配
                res = middle
                high = middle - 1
        matched_list.append(res)
    return matched_list
A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]
n = 5
print(binary_search(A, B, n))

上述代码运行后输出为[2, 0, -1, 0, -1]，和题目示例要求的结果完全一致。

效率说明 #

修正后的算法时间复杂度为O(|B| * log|A|)，就算A的长度达到10万、B的长度达到10万，总运算量也仅为10万 * 17 ≈ 170万次，完全不会出现程序卡死的情况。原代码因为存在无限死循环，实际运算量是无上限的，才会导致VS Code崩溃。

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