1.概念
二分查找也叫折半查找,是一种普遍的查找方式
2.算法使用条件
1.必须采用顺序存储结构
2.必须按关键字的大小有序排列
3.本次案例采用升序
3.查找方式
序列中间位置的值与查找的值比较如果相等查找结束,如果比中间值大,去掉中间值左边,将右边作为新的序列进行查找,如果小则相反,如此循环,直到查完列表。
4.上代码
def binary_search(data_list,value):
'''
data_list:传入有序序列
key:查找的值
'''
min_value=0 #最小下标
max_value=len(data_list)-1 #最大下标
count=1 #次数
while min_value<=max_value:
cur=(max_value+min_value)//2 #取中间值
if data_list[cur]==value:
return '查找次数为%d在data_list的索引为%d'%(count,cur)
elif data_list[cur]>value:
max_value=cur-1
else:
min_value=cur+1
count+=1
return '一共找了%d次,找不到这样的值'%count
print(binary_search([2,3,4,5,6],6))
#二分查找求值的平方根(近似值)
x=25
epsilon=0.01
step=epsilon**2
numGuess=0
ans=0.0
#用穷举法找到那个最相近的值
while abs(ans**2-x) >= epsilon and ans<=x:
ans+=step
numGuess+=1
print('numGuess',numGuess) #查找次数
if abs(ans**2-x)>=epsilon:
print('未找到平方根',x)
else:
print(ans,'是%d的平方根'%x)
5.上图片