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

文章插图
当您要检查某个元素是否在列表中时，有很多方法可以解决相同的问题。可以通过线性查找和二分查找来完成，但是要猜测哪个更快。
为什么？如果你最近参加过面试，你就会知道二分查找是面试官的最爱。
您为什么要花时间学习二分查找？ C ++编程朋友可能已经告诉过您。Python很慢。您想确保自己的程序不会比所需的速度慢。
学习Python时，您将学习进行线性查找以检查元素是否在列表中。当您学习编码时很好，但是如果列表中有60.000.000个元素会发生什么呢？
如果在包含11个元素的列表中进行线性查找，则必须遍历所有11个元素。如果您使用二分查找，最终可能要进行2次迭代，具体取决于您要查找的内容。请参见下面的图形。
显而易见，哪种方法更快。
开始学习Python时，您很可能已经使用了一百次列表。检查列表中是否有一个值是一项正常的任务，您之前已经看到过：
my_list = [1,2,3,3,5,11,12]if 11 in my_list:return Truereturn False或者
my_list = [1,2,3,3,5,11,12]for each in list:if each==11:return Truereturn False让我们开始看看如何实现二分查找。
怎么做?让我们看看二分查找是如何工作的。
首先，我们需要确保列表是有序的。您可以使用.sort()或sorts()对列表进行排序，我使用.sort()在适当的地方修改列表。如果出于某种原因需要一个新列表，或者不想篡改原始列表，可以使用sorted()
这是我们的测试内容:
bin_list = [1,2,3,5,6,9,11,12,15,20,22]search_value_a = 15我们要寻找15的值。
我们的起点。具有最小值和最大值的列表:
文章插图
当我们做二分查找时，我们从寻找列表中的中间元素开始:
文章插图
中间索引为5 ，值为9 。首先我们要知道9是不是我们要找的数字。记住，我们要找的是15 。如果不是，我们检查它是更高还是更低。在这个例子中， 9比15小，所以我们需要设置一个新的最小值点。我们知道我们不再需要担心列表的下半部分。新的最小点将被设置为列表上部的第一个可能的项。
文章插图
使用新的中点，我们检查这是否是我们要寻找的数字。在这种情况下，正好是15 ，这样这次查找就完成了。
如果我们要找的是2 ，而第一个中间值是9 ，你觉得这个算法会怎么做?你是对的。取而代之的是max指数。
文章插图
文章插图
文章插图
文章插图
代码通俗的流程解释如下：
用列表和目标作为参数创建函数。确保列表是有序的。
获取列表长度- 1为最大， 0为开始。循环将:
1. 获得新的中间值
1. 检查中间值是否高于或低于目标值。
1. 检查结束后，将最小值或最大值移到中间。
1. 如果middle == target ，返回True
1. 如果我们到达列表的末尾，则目标不在列表中
下面看看代码实现：
import randomdef binary_search(input_list , target_value):'''Function executing binary search to find if element is in a list.parameters:- list- targetreturn value: True/False (bool)'''input_list.sort()min_index = 0max_index = len(input_list) -1while 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-1return Falsedef main():#bin_list = list(range(6,501))bin_list = [1,2,3,5,6,9,11,12,15,20,22]search_value_a = 15search_value_b = 7assert binary_search(bin_list,search_value_a) == Trueassert binary_search(bin_list,search_value_b) == Falseif __name__ == '__main__':main()我们已经创建了一个具有两个参数的函数。列表和目标值。目标值就是我们要找的数字。这个列表就是我们要遍历的，用来寻找数字的列表。
def binary_search(input_list , target_value):如果我们找到了目标值，我们将返回True 。如果不是，我们将返回False 。