基于Python切片实现的二分查找：复杂度核查与低侵入优化

你对该实现的时空复杂度判断完全正确，具体推导如下：

• 时间复杂度层面：Python列表切片是值拷贝操作，而非指向原列表的视图引用。每次递归调用生成的arr[:m]、arr[m:]都会复制对应长度的所有元素，单次切片的时间开销等于当前子数组的长度。总时间开销是等比数列求和：n + n/2 + n/4 + ... ≈ 2n，整体为O(n)，远高于经典二分查找的*O(log n)*理论下限。
• 空间复杂度层面：除了递归调用栈本身的O(log n)深度开销外，每次递归的切片拷贝会占用额外堆空间，所有切片的元素总和同样趋近于O(n)，远高于原地二分的空间开销。

你担心的上下界指针方案会大幅改动代码的顾虑，可以通过保留原递归结构、仅补充内部边界参数、对外接口完全不变的方式解决，改动量极小：
原代码的核心逻辑是「计算当前子数组中点→根据中点值判断查询左/右半区间→返回对应区间的结果/偏移后的结果」，我们不需要重构这个逻辑，仅需把「传切片」替换为「传原列表的全局边界索引」，同时通过可选参数保证对外调用和原接口完全兼容，优化后代码如下：

def bin_search(arr, key, low=None, high=None):
    # 首次调用时初始化边界，对外完全兼容原接口
    if low is None:
        low = 0
    if high is None:
        high = len(arr)
    n = high - low  # 用边界差计算当前子数组长度，无需切片
    if n < 2:
       return (low if (n == 1 and arr[low] == key) else None)
    m = low + int(0.5 * n)  # 中点基于全局偏移计算，逻辑和原代码完全一致
    if arr[m] > key:
       return bin_search(arr, key, low, m)  # 传边界替代切片拷贝
    return bin_search(arr, key, m, high)

该优化的优势：

• 零侵入对外接口：原函数名、必选参数、返回值规则完全未变，所有原有调用代码无需任何修改
• 时空复杂度降为理论最优：时间复杂度回到O(log n)，空间复杂度仅保留递归栈本身的*O(log n)*开销，无额外拷贝成本
• 核心逻辑完全沿用原代码：仅修改了长度计算、中点偏移、递归传参三处，未重构原有判断流程，符合最小改动要求

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