为什么我的二分搜索比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

列表切片是O(k),其中k是您获得的切片的长度.您split_list()在行中重复切片列表return sorted_list[:half], sorted_list[half:].bisection调用split_list()整个列表的顶级调用将仅运行O(n)split_list(因为左半部分的大小+右半部分的大小= n),这本身已经与时间复杂度相匹配线性搜索.

得到一个办法解决这个,而不是名单切片,围绕传递lowerBound和upperBound在递归调用你的函数(其中上层呼叫使用lowerBound和upperBound设置0,并 len(sorted_list)分别).而且length_of_list会upperBound - lowerBound.