Python二分搜索函数为何未执行return语句？返回None而非False

问题根源 #

• 递归调用未返回结果：在x < elements[i]和x > elements[i]的分支中，调用递归函数bi_search(e, x)时未使用return返回执行结果。这导致递归完成后，当前层级函数无返回值，Python默认返回None。即便最底层递归返回了False，该结果也无法传递到顶层函数。
• 中间索引计算逻辑有缺陷：原代码用len(elements)/2-1做浮点除法后转整数，在部分列表长度下会出现不符合预期的索引。比如列表长度为3时，3/2-1=0.5转int后为0，直接触发return False，但此时仍有可查找的元素。

修复后的代码 #

def bi_search(elements: list, x) -> bool:
    if not elements:  # 空列表直接返回False，覆盖所有元素不存在的终止场景
        return False
    i = len(elements) // 2  # 整数除法直接取中间索引，避免浮点运算误差
    print(i)
    if x == elements[i]:
        return True
    elif x < elements[i]:
        return bi_search(elements[:i], x)  # 返回递归结果，逐层传递
    else:
        return bi_search(elements[i+1:], x)  # 返回递归结果，逐层传递

修复说明 #

1. 空列表判断：将空列表作为递归终止条件，比判断i==0更严谨，能覆盖所有元素不存在的情况。
2. 修正索引计算：用len(elements)//2直接获取中间索引，符合二分搜索的标准逻辑，避免浮点运算带来的错误。
3. 返回递归结果：在递归分支添加return，让底层递归的结果逐层传递回顶层函数，确保最终返回正确的True或False。

测试执行示例：

my_list = [1, 2, 5, 7, 8, 10, 20, 30, 41, 100]
print(bi_search(my_list, 21))  # 输出False
print(bi_search(my_list, 7))   # 输出True

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