二分法查找算法的时间复杂度,二分搜索算法的时间复杂度为

  二分法查找算法的时间复杂度,二分搜索算法的时间复杂度为

  如何理解二分搜索法?当我们查字典和电话时,有两种方法可以查。一种是简单查,从头开始,从字母A开始逐页查;第二种方法是近似二分搜索法。如果要查询以X开头的名字,我们会直接翻到字典的后半部分,而不是从第一页开始翻到字母X的位置。

  二分搜索法的意思是每次你从中间开始看。比如我们要从1-100中找出一个数字,比如80。根据二分搜索法方法,首先检查100/2=50,50小于80,然后检查75,它仍然小于80,然后检查87,它大于80。接下来,将75-87的中间数与80进行比较,最终找到80。那么对于从1到100的100个数字,二分搜索法最多需要查多少次呢?答案是log(100)。每次取一半,相当于每次除以2,总共是100个数。我们要计算的是我们需要除以2的次数。

  这样,二分搜索法比简单的搜索更方便有效。但是二分搜索法必须在有秩序的情况下进行。如果字典和电话簿不是按字母顺序排列的,如果1-100的数字不是按升序排列的,那么二分搜索法就没有意义。

  至于时间复杂度,从字面上理解是用时间复杂度来计算整个算法花费的时间,但用整个算法的增长率来解释更准确。如上所述,二分搜索法的时间复杂度是O(log100),如果是N,那么时间复杂度就变成O(logn);相比较而言,简单搜索的时间复杂度为O(n)。

  从上图来看,一开始两者差别不大,但是当数量级变成一亿或者一亿的时候,简单搜索的速度和时间复杂度要远远高于二分搜索法。

  代码实现(python)

  def binarySearch(list,Target):lo=0 hi=len(list)-1 while lo=hi:mid=(lo hi)//2 if list[mid]=Target:return mid elif list[mid]Target:lo=mid 1 else:hi=mid-1 return none参考:了解来自《算法图解》

二分法查找算法的时间复杂度,二分搜索算法的时间复杂度为