python3实现折半查找（win7）

现实利用中有时要对一个序列或者列表数值进行查找，折半查找作为一种简单利用的有序列表查找方式，比力常用。

工具/原料

python3 pycharm
windows7情况

方式/步骤

1
简介：
折半查找，也称二分罚查找，是针对有序数列进行查找的方式。比拟于挨次查找，利用折半查找算法的效率更高。
也就是说：
1）对一个无序数列，首先要排序；
2）然后设定头从头至尾2个指针，计较 mid(中心位置) = （头+从头至尾）/2
3）用中心位置数值元素和方针值比力，若是中心元素正好是要查找的元素，则搜刮过程竣事；若是方针元素大于或者小于中心元素，则在数列大于或小于中心元素的那一半中查找，并且继续从新计较的中心元素起头比力。若是在计较获得数据为空，则代表没找到。
折半查找的规模不竭缩小一半，所以查找效率较高。
2
输入随机数列 [6, 2, 7, 10, 23, 13, 15] 然后查找 13是否存在
首先进行排序
listNumSort = sorted(listNum)
然后进行折半搜刮
颠末三趟处置后找到方针数据。完当作搜刮。
3
1）利用构建随机数列
2）从数列随机挑一个数作为方针数字
3）排序
4）查找
import randomimport timeimport numpy as np
listNum = 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