python3实现折半查找（win7）

2025-11-09 01:56:06

1、简介：

折半查找，也称二分罚查找，是针对有序数列进行查找的方法。相比于顺序查找，使用折半查找算法的效率更高。

也就是说：

1）对一个无序数列，首先要排序；

2）然后设定头尾2个指针，计算 mid(中间位置) = （头+尾）/2

3）用中间位置数值元素和目标值比较，如果中间元素正好是要查找的元素，则搜索过程结束；如果目标元素大于或者小于中间元素，则在数列大于或小于中间元素的那一半中查找，而且继续从新计算的中间元素开始比较。如果在计算得到数据为空，则代表没找到。

折半查找的范围不断缩小一半，所以查找效率较高。

python3实现折半查找（win7）

2、输入随机数列 [6, 2, 7, 10, 23, 13, 15] 然后查找 13是否存在

首先进行排序

listNumSort = sorted(listNum)

然后进行折半搜索

经过三趟处理后找到目标数据。完成搜索。

python3实现折半查找（win7）

3、��使用构建随机数列

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))

python3实现折半查找（win7）

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

python3实现折半查找（win7）