2022年 11月 7日

用Python实现二分法查找

关于二分法的定义我就不说了，CSDN很多大牛和前辈都已经阐述的很清楚了，直接上代码。

首先，先创建一个名称为 binary_search 的函数：传递两个参数，元素列表和要查找的值。

def binary_search(_list, value):

接下来，在函数内部定义所需的变量，二分法的关键在于从列表的中间向两侧查找（表述可能不严谨，大概这个意思），所以为了直观起见，定义 left，right， mid 三个变量，分别代表：列表的起始索引，结束索引和中间索引。

  1.     left = 0   # 列表的起始索引
  2.     right = len(_list)   # 列表的结束索引
  3.     mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

接下来是实现二分查找的关键部分，先定义一个while循环，使得查找可以顺利进行，while函数内嵌套 if 分支语句实现条件判断，共有三种情况：

1. _list[mid] == value: 中间值恰好是我们需要查找的值，那么直接返回对应的索引就可以了。

2. _list[mid] > value: 要查找的值在mid的左侧，更新right 的值为mid，缩小查找范围。

3._list[mid] < value:要查找的值在mid的右侧，更新left 的值为mid，到 mid 右侧进行查找。

最后，对mid的值做一下更新，以便开始下一轮查找，同时采用 while-else语句针对没有查找到的情况进行判断，并给定一个返回值。

  1.     while left < right:
  2.         if _list[mid] == value:
  3.             return mid
  4.         elif _list[mid] > value:
  5.             right = mid
  6.         else:
  7.             left = mid
  8.         mid = int((right + left)/2)
  9.     else:
  10.         return -1

最后，完整代码，以及测试运行表现如下：

  1. """ a demo realize binary search"""
  2.  
  3.  
  4. def binary_search(_list, value):
  5.     left = 0   # 列表的起始索引
  6.     right = len(_list)   # 列表的结束索引
  7.     mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
  8.     while left < right:
  9.         if _list[mid] == value:
  10.             return mid
  11.         elif _list[mid] > value:
  12.             right = mid
  13.         else:
  14.             left = mid
  15.         mid = int((right + left)/2)
  16.     else:
  17.         return -1
  18.  
  19.  
  20. index = "the index of value in the list: {}"
  21. print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

运行结果：

 没有要查找的值的情况：