如何修复'NoneType' object is not subscriptable错误及代码排查

错误原因 #

• array.sort()赋值导致array变为None：list.sort()是原地排序方法，执行后直接修改原列表，返回值为None。代码中array = array.sort()会把None赋值给array，后续访问array[i]或array[mid]时，就会触发'NoneType' object is not subscriptable错误。
• 递归返回值结构错误：二分搜索的递归分支中，返回的是(binary_search(...), counter)，这会导致返回结果为嵌套元组（如((mid, counter), counter)），后续解包result, binaryComparisons时会抛出值数量不匹配的错误，同时统计的比较次数也会出错。
• 索引越界风险：循环中range(1, n + 1)会让i取到n，而列表索引从0开始，array[i]会超出有效索引范围。
• 二分搜索初始边界错误：调用binary_search时传入的end参数是len(array)，但二分搜索的end应为列表最后一个元素的索引（即len(array)-1），否则当查找元素大于所有元素时，mid会等于len(array)，访问array[mid]会触发索引越界。

解决方法 #

针对上述问题，逐一修正：

1. 修正列表排序方式：
   去掉赋值操作，直接使用array.sort()（原地修改列表），或者用array = sorted(array)（返回新的排序后列表）。建议在循环外只排序一次，避免重复排序浪费性能。

2. 修复递归返回值：
   递归分支直接返回binary_search的调用结果，因为递归调用已经返回了(索引, 比较次数)的元组，无需额外拼接counter。

3. 修正循环索引范围：
   将range(1, n + 1)改为range(n)，遍历列表所有有效索引（0到n-1）。

4. 修正二分搜索初始边界：
   调用binary_search时，end参数传入len(array)-1，确保索引始终有效。

修改后的完整代码 #

def binary_search(array: list, element: int, start: int, end: int, counter: int) -> tuple[int, int]:
    counter += 1
    # 处理元素不存在的情况，返回-1和当前比较次数
    if start > end:
        return -1, counter
    
    mid = (start + end) // 2
    
    if element == array[mid]:
        return mid, counter
    elif element < array[mid]:
        return binary_search(array, element, start, mid - 1, counter)
    else:
        return binary_search(array, element, mid + 1, end, counter)

array = parse("input.txt")
n = len(array)  # 若size是自定义获取长度的函数，可保留size(array)
binaryComparisonsSum = 0

# 提前排序，避免循环内重复执行
array.sort()

for i in range(n):
    result, binaryComparisons = binary_search(array, array[i], 0, len(array)-1, 0)
    binaryComparisonsSum += binaryComparisons

额外说明：

• 新增start > end的判断，处理目标元素不存在的情况，避免递归无限调用或索引越界。
• 返回类型标注改为tuple[int, int]，符合Python 3.9+的标准类型语法。

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