1、简介：折半查找，也称二分罚查找，是针对有序数列进行查找的方法。相比于顺序查找，使用折半查找算法的效率更高。也就是说：1）对一个无序数列，首先要排序；2）然后设定头尾2个指针，计算 mid(中间位置) = （头+尾）/23）用中间位置数值元素和目标值比较，如果中间元素正好是要查找的元素，则搜索过程结束；如果目标元素大于或者小于中间元素，则在数列大于或小于中间元素的那一半中查找，而且继续从新计算的中间元素开始比较。如果在计算得到数据为空，则代表没找到。折半查找的范围不断缩小一半，所以查找效率较高。
2、输入 随机数列[6, 2, 7, 10, 23, 13, 15] 然后查找 13是否存在首先进行排序listNumSort = sorted(listNum)然后 进行折半搜索经过三趟处理后 找到目标数据。完成搜索。
3、1）使用构建随机数列2）从数列随机挑一个数作为目标数字3） 排序4）查找import randomimport timeimport numpy as nplistNum = random.choices(range(1, 34), k=10, weights=range(1, 34))listNum = [6, 2, 7, 10, 23, 13, 15] #演示例子aimNum = random.choices(listNum, k=1)[0]# aimNum = random.choices(listNum)print(listNum, aimNum)print("--------随机数列-----------")listNumSort = sorted(listNum)print(listNumSort)print("-------排序完成------------")print(BinarySearch(listNumSort, aimNum))
4、查找函数，为看的明显一点，加了注释def BinarySearch(listNum, aimNum): lowpos = 0 highpos = len(listNum) - 1 print("当前头坐标：lowpos = {}, 尾坐标 highpos={}".format(lowpos, highpos)) i = 0 while(1): i = i + 1 print("第 %d 趟"%i) if(lowpos <= highpos): midpos = lowpos + (highpos - lowpos) // 2 midNum = listNum[midpos] print(" ", end='') print(listNum, aimNum) print("当前头坐标lowpos = {},尾坐标highpos={},新中值坐标midpos = {},新中值midNum={}".format(lowpos, highpos, midpos , midNum)) if midNum == aimNum: print(listNum, aimNum) print("找到！ 当前头坐标lowpos = {},尾坐标highpos={},新中值坐标midpos = {},新中值midNum={}".format(lowpos, highpos, midpos,midNum)) return midpos elif midNum < aimNum: lowpos = midpos + 1 print(" ", end='') print(listNum, aimNum) print(" 新中值小于目标值 头坐标后移1：当前头坐标lowpos = {},尾坐标highpos={},新中值坐标midpos = {},新中值midNum={}".format(lowpos, highpos, midpos,midNum)) else: highpos = midpos - 1 print(" ", end='') print(listNum, aimNum) print(" 新中值小于目标值 尾坐标前移1：当前头坐标lowpos = {},尾坐标highpos={},新中值坐标midpos = {},新中值midNum={}".format(lowpos, highpos, midpos,midNum)) return None
5、排序：[6, 2, 7, 10, 23, 13, 15] 13变成[2, 6, 7, 10, 13, 15, 23]
6、一趟搜索第 1 趟 [2, 6, 7, 10, 13, 15, 23] 13当前头坐标lowpos = 0,尾坐标highpos=6,新中值坐标midpos = 3,新中值midNum=10 [2, 6, 7, 10, 13, 15, 23] 13 新中值小于目标值 头坐标后移1：当前头坐标lowpos = 4,尾坐标highpos=6,新中值坐标midpos = 3,新中值midNum=10
7、二趟：第 2 趟 [2, 6, 7, 10, 13, 15, 23] 13当前头坐标lowpos = 4,尾坐标highpos=6,新中值坐标midpos = 5,新中值midNum=15 [2, 6, 7, 10, 13, 15, 23] 13 新中值小于目标值 尾坐标前移1：当前头坐标lowpos = 4,尾坐标highpos=4,新中值坐标midpos = 5,新中值midNum=15
8、三趟：找到！第 3 趟 [2, 6, 7, 10, 13, 15, 23] 13当前头坐标lowpos = 4,尾坐标highpos=4,新中值坐标midpos = 4,新中值midNum=13[2, 6, 7, 10, 13, 15, 23] 13找到！ 当前头坐标lowpos = 4,尾坐标highpos=4,新中值坐标midpos = 4,新中值midNum=13
