用python实现二分查找,超级详细,图片加案例

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.上图片

用python实现二分查找,超级详细,图片加案例

 

上一篇:Infinite Tree


下一篇:第一次作业(C语言)