基于递归和列表切片的recursive binary search实现问题咨询

现有代码的核心问题 #

• 递归调用binary_search时未添加return关键字，内层递归的返回值无法向外传递，即使匹配到目标值，最终也只会返回None
• 没有设置递归终止条件：当切片后的列表为空时，说明目标值不存在，需直接返回False，否则空列表访问下标会抛出索引越界异常
• 切片范围包含了已经判断过的mid位置元素，会产生冗余判断，极端情况下还会触发死递归

修复后的代码 #

def binary_search(iterable, target):
    # 终止条件：列表为空代表未找到目标
    if not iterable:
        return False
    
    mid = len(iterable) // 2
    if iterable[mid] == target:
        return True
    elif iterable[mid] < target:
        # 向右半部分查找，跳过已判断的mid位置，必须return递归结果传递到外层
        return binary_search(iterable[mid+1:], target)
    else:
        # 向左半部分查找，跳过已判断的mid位置
        return binary_search(iterable[:mid], target)

逻辑说明 #

• 入参仅保留iterable和target两个，完全符合你简化入参的要求
• 原代码中声明的left_index、right_index变量无额外作用，直接通过切片隐含的边界即可实现逻辑
• 若需要保留调试打印逻辑，可在递归调用前添加对应的print(iterable)语句，不影响核心运行逻辑

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