Python递归二分查找函数存在问题，寻求调试帮助

你的代码存在几个关键问题： #

• 混合了循环与递归：递归二分搜索不需要while循环，每次递归只需要处理当前子列表的一次中间值判断，循环会打乱递归的逻辑流程。
• 切片范围错误：
  • 当lyst[mid] < target时，目标值应该在mid+1到列表末尾的区间里，你当前切片lyst[left: right]不仅没跳过mid，还会丢失原列表的right位置元素（Python切片是左闭右开）。
  • 当lyst[mid] > target时，目标值应该在列表开头到mid-1的区间里，你用lyst[left: (right + 1)]完全没缩小正确范围。
• 空列表判断位置滞后：应该在函数最开头就判断空列表，否则递归到空列表时，会先执行left = 0、right = len(lyst)-1（此时right为-1），进而触发错误的索引访问。

修正后的代码（无需辅助函数） #

def binary_search(lyst, target):
    # 先处理空列表的情况
    if not lyst:
        return False
    
    mid = len(lyst) // 2
    if lyst[mid] == target:
        return True
    elif lyst[mid] < target:
        # 目标在右半部分，从mid+1开始到末尾
        return binary_search(lyst[mid+1:], target)
    else:
        # 目标在左半部分，从开头到mid-1
        return binary_search(lyst[:mid], target)

补充：如果允许使用辅助函数（更高效，避免切片开销） #

虽然你不确定是否能用辅助函数，但可以提一下这种更优的实现——通过辅助函数维护上下界，避免每次递归切片产生新列表：

def binary_search(lyst, target):
    def helper(left, right):
        if left > right:
            return False
        mid = (left + right) // 2
        if lyst[mid] == target:
            return True
        elif lyst[mid] < target:
            return helper(mid + 1, right)
        else:
            return helper(left, mid - 1)
    
    return helper(0, len(lyst)-1)

这种方式不会创建新的子列表，性能更好，而且逻辑更清晰，符合标准的递归二分搜索实现。

测试验证 #

用你的测试案例验证：

• 对于[1,2,3,4,5,6,7,8,9,10]，搜索3会正确返回True
• 对于[1,2,3,...,15]，搜索3也能正确返回True

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