Python递归实现二分查找函数陷入无限循环问题求助

嘿，我来帮你揪出这段递归二分查找代码里的问题，看看为啥会无限循环～

核心问题分析 #

你的代码里有几个关键错误，直接导致了无限循环和逻辑混乱：

1. 递归调用没传递边界参数i和j
   每次递归调用search(lst, v)的时候，新的函数实例里根本没有i和j这两个变量，所以每次都会重新执行i=0、j=len(lst)。相当于每次递归都从头开始搜索，完全没缩小范围，这不无限循环才怪！

2. 每次递归都排序列表
   lst.sort()是原地排序操作，你每次进入函数都排一遍，这不仅纯纯浪费性能，还会彻底打乱元素的位置——前一次递归确定的搜索范围，排序后直接失效，逻辑完全乱套了。排序只需要在最开始做一次就够了。

3. 初始边界j的取值错误
   你把j初始设为len(lst)，但列表的最大有效索引是len(lst)-1，这会导致计算midindex时可能超出列表范围，触发索引越界错误。

修正后的代码 #

我帮你调整了代码，解决了这些问题，还加了未找到时的终止条件：

def search(lst, v, i=None, j=None):
    # 第一次调用时初始化参数并完成排序
    if i is None and j is None:
        # 用sorted生成新的排序列表，避免修改原列表
        sorted_lst = sorted(lst)
        return search(sorted_lst, v, 0, len(sorted_lst) - 1)
    
    # 递归终止条件：搜索范围为空，说明目标值不存在
    if i > j:
        return -1
    
    # 计算中间索引，用整数除法更稳妥
    midindex = i + (j - i) // 2
    
    if lst[midindex] > v:
        # 目标值在左半区，缩小右边界
        return search(lst, v, i, midindex - 1)
    elif lst[midindex] < v:
        # 目标值在右半区，扩大左边界
        return search(lst, v, midindex + 1, j)
    else:
        # 找到目标值，返回索引
        return midindex

修正点说明 #

• 把i和j设为可选参数，第一次调用时自动初始化，递归时传递更新后的边界，真正实现范围缩小。
• 排序只在第一次调用时执行一次，用sorted生成新列表，避免修改原列表（如果允许修改原列表，也可以换成lst.sort()再初始化边界）。
• 添加了i > j的终止条件，当搜索范围耗尽时返回-1，避免无限循环。
• 用//整数除法替代int((j-i)/2)，更符合Python的整数运算逻辑，也避免浮点数转换的潜在问题。

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