二分查找会更快吗？Python中的二分查找与线性查找性能测试( 二 ) 当您要检查某个元素是否在列

我们要做的第一件事是对列表进行排序，并定义列表的最小索引和最大索引。
input_list.sort()min_index = 0max_index = len(input_list) -1我们使用len(list)-1的原因是Python从0开始索引。测试列表的长度是11 ，但是最后一个索引是[10] 。
现在，让我们进入主要的功能，循环:
while max_index >= min_index:mid_index =(max_index+min_index)//2if input_list[mid_index] == target_value:return Trueelif input_list[mid_index] < target_value:min_index = mid_index+1else:max_index = mid_index-1只要最大值不大于最小值，我们就继续。如果循环停止了，那就意味着我们已经折叠了列表，使得最大值小于最小值。此时，没有必要查找这个值，因为没有更多的列表了。
mid被设置为最大值和最小值的平均值。请注意我们是如何使用整数除法的，例如7//2将是3而不是3.5 。这样，我们总是为索引得到一个干净的整数。
如果带有中间索引的列表项的值等于我们的目标值，我们就成功了!返回True ，然后退出。
如果这个值小于目标值，我们知道我们必须把最小索引推到那个点。因此新的最小值是中间+1
如果该值不等于或小于目标值，则会较大。这意味着我们可以删除列表的顶部并将最大索引下压。 max被设置为中间-1
如果您觉得难以理解，可以在代码中添加print() ，以获得索引跳跃的可视化表示。
在while循环的midindex =(maxindex+min_index)//2之后添加这个:
print (f'min: {min_index} , mid: {mid_index} , max: {max_index}')但是它更快吗?该函数的时间复杂度为O(n) ，其中n为链表的长度。为了检验哪种查找更快，我们可以计算二分查找相对于线性查找的时间。
文章插图
首先，我们需要写出一个线性查找函数:
def linear_search(input_list, target_value): for each in input_list: if each==target_value: return True return False下面我们可以进行对比了：
def binary_performance():run_setup = '''from __main__ import binary_search'''run_code = '''bin_list = list(range(6,501))binary_search(bin_list,15)'''performance = timeit.repeat(setup = run_setup,stmt = run_code,repeat = 3,number = 10_000)print(f'binary search performance = {round(min(performance),2)}')def linear_performance():run_setup = '''from __main__ import linear_search'''run_code = '''lin_list = list(range(6,501))linear_search(lin_list,15)'''performance = timeit.repeat(setup = run_setup,stmt = run_code,repeat = 3,number = 10_000)print(f'linear search performance = {round(min(performance),2)}')binary_performance()linear_performance()
文章插图
陷阱如果您运行上面的代码(与原始代码合并) ，您将看到线性查找更快了。这是什么魔法?
有几个问题给二分查找带来了困难。
排序
列表的长度
低于目标的值
以上所有因素，让线性领先。现在让我们继续排序，先改变列表长度:
bin_list = list(range(1,10000))lin_list = list(range(1,10000))
文章插图
线性查找仍然占上风。让我们对函数进行排序，并在将列表传递给函数之前对其进行排序。 (这对线性查找是不公平的，因为线性并不依赖于排序列表) 。我们所要做的就是在列表排序时注释掉它。
文章插图
二者速度比较接近了。
如果我们将目标值移动到7,500呢?现在我们的偏差很明显，因为我们真的想让二分更快。
文章插图
这次的差异是极端的。下面的最后一个例子将使情况更加公平。
让我们以随机长度和随机目标创建一个随机列表。然后我们将为这两个函数运行100,000次。
test_list = list(range(1,random.randint(2,50000)))test_number = random.randint(2,50000)binary_search(test_list,test_number)
文章插图
文章插图
现在让我们运行10万次! ，我相信这些结果。上图是排序后结果，下图需要进行排序
总结二分比线性快吗?是的，但要看情况而定。
如果有人告诉你二分查找更快，那是因为它通常是更快的。
和往常一样，你必须看一看设置，不要每次都去找一个单一的解决方案，因为它"是最好的" 。