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