1、二分法作用

从有序列表的候选去 data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

2、二分查找思路

2.1、二分法查找来查找 3

首先定义2个变量，一个最小值low(值：0 )，最大值high(值：len(list变量)-1 )，中间值mid：(值：(low+high)//2 )：
image.png
第1次查找的时候发现 3 的值 比中间值小，所以最大值high的值则为：mid-1：
image.png
这个时候mid的值也发生了变化，这个时候mid的值由(low+high)//2 得出 2：
image.png
接下来发现中间值 mid < 3，所以这个时候low的值不再是0，而是切到 mid(中间值的) 左边，low值 (mid+1)：
image.png
那么这个时候的mid(中间值：(low+high)//2)，算出 mid = 3：
image.png

3、二分法实现

3.1、二分法实现

根据上述的逻辑思路，我们这边用python的代码逻辑实现。

  1. data_set = [1,2,3,4,5,6,7,8,9]  #创建的1-9的list
  3. def bin_search(data_set,val):
  4.     low = 0       #定义最小值下标值(index)
  5.     high = len(data_set) - 1 #获取最大下标值(index)
  6.     while low <= high:    #如上图 low是 一直 <= high
  7.         mid = (low+high)//2    #获取中间值
  8.         if data_set[mid] == val:     #查到了，则返回下标值
  9.             return mid
  10.         elif data_set[mid] < val: #如果大于中间值，则需要从右边查找了，那么low值就要向右移动
  11.             low = mid + 1
  12.         else:                      #如果小于中间值，就需要从左边查找了，那么high的值就向左边移动
  13.             high = mid - 1
  14.     return            #当没有找到的时候，直接return，则返回None
  16. val_index = bin_search(data_set,3)
  17. print(val_index)

上面的代码逻辑是很简单的，但是还有一种用递归的方式去写

3.2、递归方式实现

说明：递归方式我们不用，但是要知道，我只是给大家暂时，没有必要知道，只做参考，慢的原因：因为使用了切片，这个效率不高

  1. data = [1,3,6,7,9,12,14,17,18,20,21,22,23,30,32,33,35]
  4. def binary_search(dataset,find_num):
  5.     print(dataset)
  7.     if len(dataset) > 1:
  8.         mid = int(len(dataset)/2)
  9.         if dataset[mid] == find_num:
  10.             print("找到数字",dataset[mid])
  11.         elif dataset[mid] > find_num:
  12.             print("找的数字在mid[%s]左边"%dataset[mid])
  13.             return binary_search(dataset[0:mid],find_num)
  14.         else:
  15.             print("找的数字在mid[%s]右边"%dataset[mid])
  16.             return binary_search(dataset[mid+1:],find_num)
  17.     else:
  18.         if dataset[0] == find_num:
  19.             print("找到数字",dataset[0])
  20.         else:
  21.             print("没的分了，要找的数字[%s]不在列表里"%find_num)
  23. binary_search(data,66)

4、练习

1、现有一个学员信息列表(按id增序排列)，格式为：

  1. [
  2. {id:1001,name:"张三",age:20},
  3. {id:1002,name:"李四",age:25},
  4. {id:1004,name:"王五",age:23},
  5. {id:1007,name:"赵六",age:33},
  6. ]

2、修改二分法查找代码，输入学生id，输出该学生的在列表中的下标，并输出完整的学生信息。