Python递归二分搜索函数报错求助：索引类型错误

错误原因分析 #

触发TypeError: list indices must be integers or slices, not float的核心原因是计算中间索引mid时使用了普通除法/，该操作返回浮点数，而Python列表要求索引必须是整数类型。需改用整数除法//确保结果为整数。

满足计数要求的修正实现 #

递归调用计数和目标比较计数需用可变对象（比如列表）传递，因为整数是不可变类型，递归内部的修改无法同步到外部。以下是完整的binary_search()实现：

def binary_search(arr, target, low, high, recursion_count, compare_count):
    # 递归调用计数+1
    recursion_count[0] += 1
    
    # 基准情况：未找到目标
    if low > high:
        return -1
    
    # 计算整数类型的中间索引
    mid = (low + high) // 2
    
    # 目标比较计数+1
    compare_count[0] += 1
    if arr[mid] == target:
        return mid
    # 目标比较计数+1（与mid值的大小比较）
    compare_count[0] += 1
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1, recursion_count, compare_count)
    else:
        return binary_search(arr, target, mid + 1, high, recursion_count, compare_count)

使用示例 #

# 测试用有序列表
test_arr = [1, 3, 5, 7, 9, 11, 13]
target_val = 7

# 初始化计数（用列表包裹实现可变传递）
recursion_count = [0]
compare_count = [0]

result = binary_search(test_arr, target_val, 0, len(test_arr)-1, recursion_count, compare_count)

print(f"目标索引: {result}")
print(f"递归调用次数: {recursion_count[0]}")
print(f"目标比较次数: {compare_count[0]}")

错误栈对应修正说明 #

如果原代码中mid的计算是mid = (low + high) / 2，替换为mid = (low + high) // 2即可解决浮点数索引问题。同时通过列表传递计数变量，确保递归过程中计数能被正确累计。

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