开发者社区> 辣条!> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Python语言二分法查找

简介: Python语言二分法查找Python语言二分法查找
+关注继续查看

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

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

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

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

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

步骤4:查找页码对比中位数,确定新的查找范围 步骤5:循环以上步骤,直到找到该页码为止

.......

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

模拟页码

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检索用循环方式找数字21,他是排在11位,中位数查询3次,使用Python二分法检索递归方式先取查询数字的倍数,然后锁定前半段进行索引,索引的步骤耗时更少

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
python语言简介及开发环境搭建的详细介绍
第一节:计算机是什么第二节:开发前的准备 第二章 python简介及环境搭建 完成了前面python开发前的准备,从这节课开始我们将会为大家介绍python语言是怎么编程的。 2.1计算机语言简介 之前的章节内容里面为大家介绍过,计算机就是一台用来计算的机器,执行人类发出的指令。
1015 0
Python 语言简介
Python是一种计算机程序设计语言。你可能已经听说过很多种流行的编程语言,比如非常难学的C语言,非常流行的Java语言,适合初学者的Basic语言,适合网页编程的JavaScript语言等等。 那Python是一种什么语言? 首先,我们普及一下编程语言的基础知识。
1442 0
Python编程:six库兼容Python 2 和 Python 3
six 它是一个专门用来兼容 Python 2 和 Python 3 的库
8 0
Python编程:实现消息发布/订阅模型
Python编程:实现消息发布/订阅模型
6 0
Python编程:使用os.urandom生成Flask的SECRET_KEY
Python编程:使用os.urandom生成Flask的SECRET_KEY
12 0
Python编程:使用os.urandom生成Flask的SECRET_KEY
Python编程:使用os.urandom生成Flask的SECRET_KEY
12 0
python编程-15:图形库的应用方法graphics
python编程-15:图形库的应用方法graphics
10 0
Python编程:Flask或者Jinja2时间格式化
Jinja2 模板支持python函数,直接使用事件对象的方法 格式化即可
10 0
Python编程:Flask数据库扩展Flask-SQLAlchemy
Python编程:Flask数据库扩展Flask-SQLAlchemy
73 0
+关注
71
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载