【从0到1学算法】二分查找法

vlambda
2020-01-28

【从0到1学算法】二分查找法

每天进步一丢丢,连接梦与想

说到算法，大家应该都会脑壳疼吧。除了应付一下面试，准备过算法，也接触过不少算法，但是面试完了，基本上就忘光了。但不得不说，算法真的很重要，算法是解决问的方法，你可能会说根本用不上，那只是因为你根本没有算法的思维，又如何说得上使用呢。

在这里，我会和大家一起重学算法，阅读《图解算法》入门算法经典书籍，然后根据个人知识进行整理与补充而编写的文章。今天讲的二分查找法，如果你对这个算法很熟请忽略或者复习一下也未尝不可。

二分查找法

先来看看最简单的查找算法，简单查找法，也可以说是美嘉算法（美嘉经常用到的算法）

假设我在1~100的数字中查找56

使用美嘉算法是这样的

需要经过56次才能得到结果!

当我们使用二分查找法的时候是这样的

从中间50开始猜

小了,排除了半的数字! 查找范围缩小至51-100,接下来猜75

大了,又排除了一半数字!查找范围缩小到51-74,接下来猜62。又大了，再猜56

只猜了4次便找到了正确答案,这就是算法的力量啊! 100个元素里,最多只需要7次便能找到答案

这就是二分查找法,每次从中间开始猜,每次可排除一半的数量

再举个例子,假设要在包含240000个单词的字典中查找一个单词,最多需要找到少步?

使用二分查找法是这样的,最多17步

简单查找法呢,最多240000步

一般而言,对于包含n个元素的列表中，用二分查找法最多需要log2n步，而简单查找最多需要n步

即二分查找法的时间复杂度为O(logn),简单查找的时间复杂度为O(n)，这里的log指的是log2，大O表示法用来表示算法快慢（下集提前预告）

二分查找算法python代码

 
   
   
 
  
    
    
  def binary_search(list, item):
  
    
    
  

  
    
    
      low = 0
  
    
    
  
  
    
    
  

  
    
    
      high = len(list) - 1
  
    
    
  
  
    
    
  

  
    
    
      while low <= high:
  
    
    
  

  
    
    
          # //表示整除
  
    
    
  
  
    
    
  

  
    
    
          mid = (low + high) // 2
  
    
    
  
  
    
    
  

  
    
    
          guess = list[mid]
  
    
    
  

  
    
    
          if guess == item:
  
    
    
  

  
    
    
              return mid
  
    
    
  
  
    
    
  

  
    
    
          elif guess > item:
  
    
    
  

  
    
    
              high = mid - 1
  
    
    
  
  
    
    
  

  
    
    
          else:
  
    
    
  

  
    
    
              low = mid + 1
  
    
    
  
  
    
    
  

  
    
    
      return None