温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何使用Python语言实现二分法查找

发布时间:2022-03-14 13:33:31 来源:亿速云 阅读:135 作者:小新 栏目:开发技术

这篇文章主要为大家展示了“如何使用Python语言实现二分法查找”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“如何使用Python语言实现二分法查找”这篇文章吧。

前言:

二分法也就是二分查找,它是一种效率较高的查找方法

假如公司新来了一个人,叫张三,他是你们公司第47个人,过了一段时间后,有些人呢看张三不爽,离职了,那这时候张三肯定不是公司第47个人了,怎么样才知道张三排第几呢,下面我们用二分法把他找出来

思路:

给你一本1000页的书籍,随机给定一个页码,如何用最快的方式找到它?如果一页一页逐步去查找,则最高需要查找一千次!那我们如何用二分法来解决这个问题呢?二分法的关键就是二分这个词。

如何使用Python语言实现二分法查找

 步骤1:设定一个页码作为中心点来将1000页分为两份,中位数的作用就是每次缩小一半查找范围,即达到开方的效果。即可以用 (首位+末位)/2 = 中位数。

如何使用Python语言实现二分法查找

 步骤2:将需要查找的页码与中位数比价,如果大于中位数则舍弃对中位数的前一半查找,反之则舍弃对后一半范围查找,达成开方效果。 步骤3:在新的查找范围重新计算出中位数 

如何使用Python语言实现二分法查找

步骤4:查找页码对比中位数,确定新的查找范围

如何使用Python语言实现二分法查找

步骤5:循环以上步骤,直到找到该页码为止

如何使用Python语言实现二分法查找

代码:

通过以上思路解析,我们知道了二分法实行步骤,接下来就通过代码来实现步骤,首先是循环实现

#模拟页码
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#设定查找页码
findNum = 1
 
#循环查找
while True:
    #获取中位数
    mid = int((low+height)/2)
    #打印中位数,查看循环次数
    print(array[mid])
    #如果中位数小于查找值,则锁定后半段
    if array[mid] < findNum:
        #重置低位数
        low = mid + 1
    #如果中位数大于查找值,则锁定前半段
    elif array[mid] > findNum:
        #重置高位值
        height = mid - 1
    #找到数字则打印该值下标,终止循环
    elif array[mid]==findNum:
        print('find it:',array[mid],' index:',mid)
        break

除了上述方式外,也可以使用递归来实现,代码更加简洁

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
 
#函数递归
#定义一个函数,给三个形参:低位值,高位值,查找值
def BinarySearch(low,height,findNum):
    #计算出中位数
    middle = (low+height)//2
    #如果中位数小于查找值,则锁定后半段
    if findNum >array[middle]:
        #重置低位数
        low = middle +1
    #如果中位数大于查找值,则锁定前半段
    elif findNum<array[middle]:
        #重置高位值
        height = middle - 1
    else:
        #找到该值并返回
        return '该值下标为:%s,值为:%s'%(middle,array[middle])
    #没有找到则调用自身继续查找
    return BinarySearch(low,height,findNum)
 
print(BinarySearch(array[0],len(array)-1,19))

总结:

如何使用Python语言实现二分法查找

根据结果反馈,使用二分法常规Python检索用循环方式找数字21,他是排在11位,中位数查询3次,使用Python二分法检索递归方式先取查询数字的倍数,然后锁定前半段进行索引,索引的步骤耗时更少

以上是“如何使用Python语言实现二分法查找”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI