Python二分查找与线性查找基准测试速度差异疑问

你测得的耗时差异属于现代CPU运行对应算法的正常表现，核心逻辑代码没有编写错误，相关结论如下：

• 二分查找时间复杂度为O(log n)，对1亿规模的有序列表，查找最坏情况（目标在列表端点）仅需执行约27次循环，每次循环仅包含算术运算、列表索引访问、数值比较三类CPU可极快执行的基础指令，总耗时十几微秒完全符合九代酷睿i5的性能水平。
• 线性查找时间复杂度为O(n)，你选取的查找目标是列表最后一个元素，需要完整遍历1亿个元素才能返回结果，九代i5执行该量级的遍历+比较操作耗时4-5秒属于正常范围。

设备卡死和算法效率无关，核心是内存溢出导致的系统换页：

• 64位Python环境中，原生列表每个元素存储的是对象指针，单指针占8字节，10亿长度的列表仅指针存储就要占用约7.5GB内存，加上Python整数对象的额外存储开销，总内存需求超过10GB。
• 普通消费级设备配置的内存一般为8GB/16GB，运行该脚本时会直接占满可用物理内存，系统被迫调用硬盘空间作为交换分区，硬盘读写速度比内存慢2-3个数量级，直接导致整机长时间无响应。

现有代码的计时逻辑和测试设计存在可调整的空间，能让测试结果更准确：

• 计时函数替换：短耗时场景下time.time()属于墙钟时间，易受系统时间调整、其他进程资源抢占影响，建议替换为精度更高、专为性能统计设计的time.perf_counter()。
• 测试样本优化：当前仅测试了查找列表末尾元素的最坏场景，若要得到更通用的性能结论，应随机选取多组查找目标重复测试，取平均耗时作为结果。
• 测试规模控制：原生Python列表内存开销较高，测试规模不要超过设备剩余物理内存上限，不要在普通消费级设备上直接创建10亿长度的原生列表。

优化后的计时装饰器参考：

import time

def second_outer(*dargs, **dkwargs):
    def outer(func):
        def inner(*args, **kwargs):
            print(*dargs, **dkwargs)
            # 替换为perf_counter提升短耗时测量精度
            start = time.perf_counter()
            func_result = func(*args, **kwargs)
            cost = time.perf_counter() - start
            print(f'Call function {func.__name__} with duration {cost:.6f}')
            return func_result
        return inner
    return outer

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