二分法查找

二分查找又称折半查找

• 优点

  • 比较次数少，查找速度快，平均性能好

• 缺点

  • 要求待查表为有序表，且插入删除困难

• 查找思路

  • 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
  • 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
  • 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

• 时间复杂度

  • 最优时间复杂度：O(1)
  • 最坏时间复杂度：O(logn)

• 二分法查找实现：

  # coding:utf-8
  
  def binary_search(alist,item):
      ‘‘‘二分法查找‘‘‘
      first = 0 #第一个元素下标
      last = len(alist) - 1 #最后一个元素下标
      while first <= last:
          mid = (first + last)//2 #中间元素下标
          # 等于中间元素，则找到
          if item == alist[mid]:
              return True
          # 小于中间元素，则查找范围在中间元素左侧
          elif item < alist[mid]:
              last = mid - 1
          # 大于中间元素，则查找范围在中间元素右侧
          else:
              first = mid + 1
      # 未找到，返回False
      return False
  
  if __name__ == "__main__":
      alist = [1,2,3,4,5,6]
      print(binary_search(alist,1))
      print(binary_search(alist,6))
      print(binary_search(alist,0))
      print(binary_search(alist,7))

   

二分法查找