二进制搜索传递列表切片而不是整个列表

Question

如果我们传递列表切片而不是整个列表（其中列表有数百万项），排序列表的二分查找会更快吗？

正常：

def binary_search(data, target, low, high):
if low > high:
    return False
else:
    mid = (low + high) // 2
    if target == data[mid]:
        return True
    elif target < data[mid]:
        return binary_search(data, target, low, mid-1)
    else:
        return binary_search(data, target, mid+1, high)

使用列表切片（我不得不稍微修改一下）：

def binary_search(data, target, low, high):
if low > high:
    return False
else:
    mid = (low + high) // 2
    if target == data[mid]:
        return True
    elif target < data[mid]:
        return binary_search(data[low:mid-1], target, 0, mid)
    else:
        return binary_search(data[mid+1:high], target, 0, high-mid)

我目前正在学习算法，所以我真的不知道这是否是最佳实践。

Answer 1

第二种方法的问题在于，这种切片会在每次迭代时从原始列表创建另一个 list 对象，这意味着：

内存分配
原始列表的内存复制

所以索引可能会变得更清晰，但实际上性能会下降，导致搜索效果相反。

Answer 2

我认为第二种方法 TimeComplexity 与普通二进制搜索相同，但 Space complexity 是不必要的增加..

您的第一个二分查找采用常量 O(1) space，这意味着算法采用的 space 对于数组中的任意数量的元素都是相同的。但是在你的第二种情况下 space 复杂性是不必要的增加 O(logn) 因此它是低效的。

二进制搜索传递列表切片而不是整个列表

binary search passing list slice instead of whole list

python

algorithm

list

binary-search