如何修复递归二分查找代码，使其渐近时间复杂度与迭代版匹配？

你的递归版二分查找比迭代版慢的核心原因是每次递归调用都通过切片创建新的子列表（alist[:midpoint]或alist[midpoint+1:]），切片操作的时间复杂度是O(k)（k为子列表长度），累加下来整体时间复杂度会从迭代版的O(log n)变成O(n log n)，远高于预期。要让递归版的渐近时间和迭代版一致，需要避免切片，改用传递索引范围的方式缩小查找区间。

修改后的递归实现 #

这里提供两种常见的优化方案：

方案1：使用内部辅助函数处理索引

def binarySearch(alist, item):
    def recursive_search(first, last):
        # 查找区间为空，返回未找到
        if first > last:
            return False
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            return True
        elif item < alist[midpoint]:
            # 在左半区间继续查找
            return recursive_search(first, midpoint - 1)
        else:
            # 在右半区间继续查找
            return recursive_search(midpoint + 1, last)
    
    # 初始化查找区间为整个列表
    return recursive_search(0, len(alist) - 1)

方案2：给原函数添加默认索引参数

def binarySearch(alist, item, first=0, last=None):
    # 首次调用时初始化last参数
    if last is None:
        last = len(alist) - 1
    # 查找区间为空，返回未找到
    if first > last:
        return False
    midpoint = (first + last) // 2
    if alist[midpoint] == item:
        return True
    elif item < alist[midpoint]:
        return binarySearch(alist, item, first, midpoint - 1)
    else:
        return binarySearch(alist, item, midpoint + 1, last)

优化说明 #

• 两种方案都通过传递first和last索引来限定当前的查找区间，完全避免了切片操作，每次递归调用的时间复杂度为O(1)
• 递归深度保持为O(log n)，因此整体渐近时间复杂度和迭代版一致，都是O(log n)
• 递归本身的栈开销在Python中对于二分查找的深度（最多约20层对于百万级列表）来说可以忽略不计

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