Python折半查找算法详解与线路故障排查实战
本文深入解析Python中的折半查找（二分查找）算法，阐述其通过不断缩小搜索范围来快速定位目标数据的原理。文章结合排序数列示例演示具体步骤，并通过线路故障排查的实际案例，展示如何利用该算法高效锁定故障点，代码完整且附带执行流程说明。
一、折半查找算法
折半查找，亦称二分查找，其核心思想是将数据集合划分为两个相等的部分。首先，将待查找的目标值（键值）与当前区间的中间值进行比对。若目标值小于中间值，则说明目标位于前半段；若大于中间值，则目标位于后半段。随后，算法会对选定的半段再次进行对半分割并继续比对，如此循环往复，直至找到目标值或确认其不存在。该算法的主要局限在于要求数据必须是已排序的序列，但其优势在于查找效率极高。
日常生活中，折半查找的思想随处可见，例如经典的猜数字游戏。游戏设定一个数字范围（如0至100），系统随机选取一个目标数字。玩家每次猜测后，系统会提示“猜大了”或“猜小了”，从而帮助玩家缩小猜测范围。玩家通常会先猜测中间值，根据反馈不断调整区间，最终锁定目标。这种通过不断缩小范围来逼近目标的策略，与折半查找算法的逻辑完全一致；若每次均选取区间中点进行猜测，即为标准的折半查找过程。
假设有一个已排序的数列：12、45、56、66、77、80、97、101、120，现需查找目标值101。使用折半查找的具体步骤如下：
步骤1：列出数据序列并确定中间值77，将目标值101与77进行比对，过程如下图所示。
步骤2：比较结果显示101大于77，表明目标值位于数列的右半部分。此时忽略左半部分数据，对右半部分数据再次进行分割以寻找新的中间值。新的中间值位于97和101之间，选取97作为比较对象，将101与97进行比对，过程如下图所示。
步骤3：比较结果显示101大于97，表明目标值仍位于右半段。忽略左半部分数据，对剩余数列再次分割寻找中间值。此次分割得到的中间值恰好为101，将目标值101与中间值101进行比对，过程如下图所示。
步骤4：比较结果显示101等于101，查找成功。补充说明：若经过多次分割仍未找到相等的值，则判定该目标值不在当前数列中。
从上述查找步骤可以看出，折半查找所需的比较次数明显少于顺序查找，这正是其核心优势：查找速度极快。
二、实例：线路故障
考虑一条长度为150米的线路，已知存在故障。第一天，维修人员已大致锁定9个疑似故障点，分别位于线路的12、45、56、66、77、80、97、101、120米处。第二天，维修人员需在这9个点中确定唯一的真正故障点（假设实际故障点位于101米处）。为了提高排查效率，维修人员采用在每段数据中间位置开始测试的策略。
具体操作如下：第一次测试选择在77米处的疑似点接通电路，结果电路接通，由此判断故障位于77米之后；第二次测试选取97米处的疑似点，电路依然接通，说明故障位于97米之后；第三次测试选取101米处，再次接通线路时电路未接通，从而确定此处为真正的故障点。整个查找过程仅经历3次测试便定位了故障点。具体实现代码如下：
def search(data, num):
"""
定义查找函数：该函数使用的是折半查找算法
:param data: 原数列data
:param num: 键值num
:return:
"""
low = 0 # 定义变量用来表示低位
high = len(data) - 1 # 定义变量用来表示高位
print("正在查找.......") # 提示
while low <= high and num != -1:
mid = int((low + high) / 2) # 取中间位置
if num < data[mid]: # 判断数据是否小于中间值
# 输出位置在数列中的左半边
print(f"{num} 介于中间故障点 {low + 1}[{data[low]}] 和故障点位置 {mid + 1}[{data[mid]}] 之间，找左半边......")
high = mid - 1 # 最高位变成了中间位置减1
elif num > data[mid]: # 判断数据是否大于中间值
# 输出位置在数列中的右半边
print(f"{num} 介于中间故障点 {mid + 1}[{data[mid]}] 和故障点位置 {high + 1}[{data[high]}] 之间，找右半边......")
low = mid + 1 # 最低位变成了中间位置加1
else: # 判断数据是否等于中间值
return mid # 返回中间位置
return -1 # 自定义函数到此结束
inp_num = 0 # 定义变量，用来输入键值
num_list = [12, 45, 56, 66, 77, 80, 97, 101, 120] # 定义数列
print("疑似故障点如下：")
for index, ele in enumerate(num_list):
print(f" {index + 1}[{ele}]", end="") # 输出数列
print("")
flag = True # 开关，用来管控是否多次查找
while flag: # 循环查找
inp_num = int(input("请输入故障点：").strip()) # 输入查找键值
if inp_num == -1: # 判断键值是否是-1
break # 若为-1，跳出循环 即结束程序
result = search(num_list, inp_num) # 调用自定义的查找函数——search()函数
if result == -1: # 判断查找结果是否是-1
print(f"没有找到[{inp_num}]故障点") # 若为-1，提示没有找到值
else:
# 若不为-1，提示查找位置
print(f"在{result + 1}个位置找到[{num_list[result]}]故障点")
char = input("本次查找结束，是否继续查找，请输入 y(Y) 或 n(N)：").strip()
if char.upper() == "N":
flag = False
程序执行结果如下图所示：
至此，关于Python折半查找算法的实现介绍完毕。如需了解更多Python折半查找相关内容，欢迎查阅本站往期文章或继续浏览后续内容，感谢大家的支持！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
