修复Binary Search索引错误后运行时长增加问题求助

原代码的核心错误 #

原代码触发IndexError的根本原因是错把low和high初始化为列表的元素值，而非索引：

if low is None:
    low = list[0]  # 取的是第一个元素的值，不是索引0
if high is None:
    high = list[-1]  # 取的是最后一个元素的值，不是索引len(list)-1

二分查找中，low和high必须代表当前查找范围的索引边界。如果列表元素是负数或远大于列表长度的数值，计算出的midpoint会远远超出列表的索引范围，直接导致索引越界。

你修改后的逻辑错误 #

你将判断条件改成和midpoint（索引值）比较，完全偏离了二分查找的核心逻辑：

if midpoint == target:  # 错误：应比较midpoint位置的元素与目标值
elif target < midpoint:

这种修改让代码彻底脱离了二分查找的区间缩小逻辑，变成无意义地比较目标值和索引值，导致midpoint持续增长，查找退化为低效遍历，所以单次耗时高达3秒。

修正后的完整代码 #

import random
import time

def binary_search(list, target, low=None, high=None):
    if low is None:
        low = 0  # 初始化索引下界
    if high is None:
        high = len(list) - 1  # 初始化索引上界
    midpoint = (low + high) // 2

    if high < low:
        return print("Target was not in the list")
    if list[midpoint] == target:
        return midpoint
    elif target < list[midpoint]:
        return binary_search(list, target, low, midpoint - 1)
    else:
        return binary_search(list, target, midpoint + 1, high)

if __name__ == '__main__':
    length = 100
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length))
    sorted_list = sorted(list(sorted_list))

    start = time.time()
    for target in sorted_list:
        binary_search(sorted_list, target)
    end = time.time()
    print("Binary search time: ", (end - start)/length, "seconds")

修正后的效果 #

修正后，代码会按照索引范围正常缩小查找区间，单次查找耗时会降到微秒级，符合二分查找O(log n)的时间复杂度预期。

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