Python实现双列表求和匹配二分查找运行速度过慢原因问询

核心问题 #

你犯了一个非常典型的逻辑错误：对s2的排序操作被放在了循环内部，每次遍历s1的元素都会重新排序一次s2。
你写的binary_search函数中，sorted(s2)被放在了生成器表达式的循环体里，假设s1长度为n，你就会执行n次O(n log n)的排序操作，整体时间复杂度直接变成O(n² log n)，远高于暴力解法的O(n²)，自然耗时更长。

修正方法 #

只需要把s2的排序操作提到循环外部，整个算法的时间复杂度就能回到你预期的O(n log n)：

def find_in(s, s2):
    start, end = 0, len(s2)-1
    while end >= start:
        mid = start + (end - start) // 2
        if s2[mid] == s:
            return True
        elif s2[mid] > s:
            end = mid - 1
        else:
            start = mid + 1
    return False

@timing
def binary_search(x : int, s1 : list, s2 : list) -> bool:
    # 提前排序，仅执行一次
    sorted_s2 = sorted(s2)
    return any(find_in(x - s, sorted_s2) for s in s1)

进一步优化建议 #

• 优先用Python标准库的bisect模块实现二分查找，它是C语言实现的，比纯Python手写的二分查找效率高很多：

import bisect

def find_in(s, s2_sorted):
    idx = bisect.bisect_left(s2_sorted, s)
    return idx < len(s2_sorted) and s2_sorted[idx] == s

• 如果没有必须用二分查找的要求，用哈希集合实现的时间复杂度可以降到O(n)，效率更高：

@timing
def set_solution(x : int, s1 : list, s2 : list) -> bool:
    s2_set = set(s2)
    return any(x - s in s2_set for s in s1)

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