python - 为什么我的二分搜索比 python 中的线性搜索慢？

Question

我在一次采访中被要求实现二分搜索以缩短搜索时间，我想到了这个。我回家测试了一下，但看起来线性搜索比我的二分搜索要好得多。我在这里做错了什么吗？

import time

sorted_list = range(0, 10000000)
needle = 9999999

def split_list(sorted_list):
    half = len(sorted_list)/2
    return sorted_list[:half], sorted_list[half:]

def bisection(haystack, needle, length_of_list):
    if len(haystack) <= length_of_list/5:
        return haystack

    first, last = split_list(haystack)
    if needle < first[-1]:
        return bisection(first, needle, length_of_list)
    else:
        return bisection(last, needle, length_of_list)

def linear_search(smaller_ist):
    for ele in smaller_list:
        if ele == needle:
            return 0

start_time = time.time()
smaller_list = bisection(sorted_list, needle, len(sorted_list))
print linear_search(smaller_list)
print("--- %s seconds ---" % (time.time() - start_time))

start_time = time.time()
print linear_search(sorted_list)
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

List slicing是 O(k) 其中 k 是你得到的切片的长度。您在 split_list() 中重复对列表进行切片，在行 return sorted_list[:half], sorted_list[half:] 中。对 bisection 的顶级调用，它在整个列表上调用 split_list()，运行 split_list 将花费 O(n)(因为左半部分的大小 + 右半部分的大小 = n)，它本身已经匹配线性搜索的时间复杂度。

解决此问题的一种方法是，在对函数的递归调用中传递 lowerBound 和 upperBound(顶级调用的位置)，而不是列表切片使用分别设置为 0 和 len(sorted_list) 的 lowerBound 和 upperBound )。 length_of_list 将是 upperBound - lowerBound。