二分查找的Python实现细节
程序员文章站
2024-03-19 21:27:28
...
为节约时间,实现细节与注意事项均放入代码注释行中了
# 二分查找(binary search):
# 若需要猜测1-100之间的一个数,可使用二分法(循环查找效率过低):
# 1、让每个问题的答案将可能的范围减半
# 2、首先问“是否大于50?”
# 3、若是,则继续问“是否大于75?”,以此类推
# 4、注意,备查序列必须是有序结构,关键字按大小排列
def binary_search(list, target):
'''
:param list:
:param target:
:return:返回待查元素的索引位置,若无则返回提示语句
'''
low_line=0
high_line=len(list)-1
index=1
while low_line<=high_line:
mid=(low_line+high_line)//2
if list[mid]==target:
return f'一共查找了{index}次,目标值在列表中的索引位置为{mid}'
elif list[mid]>target:
high_line=mid-1
elif list[mid]<target:
low_line=mid+1
index+=1
return f'该目标值不存在,一共查找了{index}次。'
if __name__ == '__main__':
L1=list(range(10))
result1=binary_search(L1,10)
print(result1)
L2=[1,2,3,4,5]
result2=binary_search(L2,5)
print(result2)
# 自然语言描述:
# 一、前置条件:
# 1、首先明确目标为使用二分法快速查找目标值在列表中的索引位置(即下标)
# 2、定义函数名称,并指定所需变量,list就是待查找列表,target就是目标值
# 3、为使用二分法,需设置下标上下限、下标中间值、循环结构、判断结构
# 4、为获知查找次数,需设一个初始值为1、并随循环次数增加的变量值index
# 二、编写细节:
# 1、将下标的初始下限设为0,初始上限设为列表长度减一
# (因为列表的索引下标是从0开始,最后一位恰好等于长度减一)
# 2、使用while循环,只要下限大于上限就终止循环执行(以免下标越界导致崩溃)
# 3、在while循环内的第一行设置mid初始值及变化公式,以供每次循环时使用
# 4、上限与下限之和除以二(相当于将查找区间对折),即为中间值,
# 为避免出现小数,应使用//地板除(将结果向下取整数)
# 5、开始逻辑判断:
# 以mid变量中存储的当前中间值为索引下标,通过list[mid]获取对应位置的列表值
# 首先判断对应列表值与目标值是否相等,若相等则返回mid变量中存储的当前下标
# 若对应列表值大于目标值,则对折搜索区间,将上限重设为mid-1(就是上一个中间值的左侧)
# 若对应列表值小于目标值,则对折搜索区间,将下限重设为mid+1(就是上一个中间值的右侧)
# 6、每循环一次,就让index=index+1,从而获取循环次数
# 7、若循环结束(即下限大于上限后)始终未能找到,则返回提示语句。
# 三、调用函数时需注意的细节:
# 1、注意,range函数的返回值的类型并不是列表,而是<class 'range'>,
# 因此需要用list函数将其转化为列表。
# 2、range函数生成的是一个左闭右开的等差序列,range(10)就是0~9,不包括10。
上一篇: 计算机视觉与深度学习(12)
下一篇: 一致性HASH算法详解