2.1 二分查找的步骤

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


2.2 二分查找的图解

二分查找 - 图1

2.3 二分查找代码

2.3.1 非递归版

  1. def binary_search(alist, item):
  2.     """二分查找"""
  4.     # 设置起始位置 获取中间值
  5.     start = 0
  6.     end = len(alist) - 1
  8.     while start <= end:
  9.         # 获取中间值
  10.         mid = (start + end)//2
  12.         if item == alist[mid]:
  13.             return True
  14.         elif item < alist[mid]:
  15.             end = mid - 1
  16.         elif item > alist[mid]:
  17.             start = mid + 1
  19.     # 没有找到想要找的数字
  20.     return False
  22. if __name__ == '__main__':
  23.     alist = [1,2,3,4,5]
  24.     print(binary_search(alist, 1))
  25.     print(binary_search(alist, 100))

2.3.2 递归版

  1. def binary_search(alist, item):
  2.     """二分查找"""
  4.     # 数列的长度
  5.     n = len(alist)
  6.     # 递归的结束条件
  7.     if n == 0:
  8.         return False
  10.     # 中间值
  11.     mid = n//2
  13.     if item == alist[mid]:
  14.         return True
  15.     elif item < alist[mid]:
  16.         return binary_search(alist[0:mid], item)
  17.     elif item > alist[mid]:
  18.         return binary_search(alist[mid+1:], item)
  20. if __name__ == '__main__':
  21.     alist = [1,2,3,4,5]
  22.     print(binary_search(alist, 1))
  23.     print(binary_search(alist, 100))

2.4 二分查找的时间复杂度

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