python有序查找算法 二分法实例解析
作者:TTyb 发布时间:2023-04-15 07:55:36
标签:python,查找,算法,二分
这篇文章主要介绍了python有序查找算法 二分法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...
但是需要注意:
待查找的序列区间单调有序
例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况:
假如arr[center]>key,说明key在arr中心左边范围;
假如arr[center]<key,说明key在arr中心右边范围;
假如arr[center]=key,说明key在arr中心。
范围每次缩小一半,写个while的死循环知道找到为止。
二分法查找非常快且非常常用,但是唯一要求是要求数组是有序的
二分法的代码如下:
#!/usr/bin/python3.4
# -*- coding: utf-8 -*-
def BinarySearch(arr, key):
# 记录数组的最高位和最低位
min = 0
max = len(arr) - 1
if key in arr:
# 建立一个死循环,直到找到key
while True:
# 得到中位数
# 这里一定要加int,防止列表是偶数的时候出现浮点数据
center = int((min + max) / 2)
# key在数组左边
if arr[center] > key:
max = center - 1
# key在数组右边
elif arr[center] < key:
min = center + 1
# key在数组中间
elif arr[center] == key:
print(str(key) + "在数组里面的第" + str(center) + "个位置")
return arr[center]
else:
print("没有该数字!")
if __name__ == "__main__":
arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
while True:
key = input("请输入你要查找的数字:")
if key == " ":
print("谢谢使用!")
break
else:
BinarySearch(arr, int(key))
运行结果:
来源:https://www.cnblogs.com/TTyb/p/5795466.html
0
投稿
猜你喜欢
- Truncate是SQL中的一个删除数据表内容的语句,用法是:TRUNCATE TABLE [Table Name]。下面是对Truncat
- 1、图片防盗链在一些大型网站中,比如百度贴吧,该站点的图片采用了防盗链的规则,以至于使用下面代码会发生错误。简单代码:<!DOCTYP
- 内容摘要:网页设计师制作网页最常用的设计软件应该就算adobe的产品Photoshop了,当然Photoshop不仅可以设计网页,不过作为网
- 前几天,为了增强本站的SEO,着手把另一个域名:www.aspxhome.com下的所有页面301转向到www.cidianwang.com
- 新一代W3C,xhtml代码规范,大家在设计网站的时候务必遵循这一规范 ,这将对网站的优化,网站的推广,搜索引擎的友好
- 下面通过实例代码给大家分享Python切片操作去除字符串首尾的空格的方法,具体内容如下所示:#利用切片操作,实现一个trim()函数,去除字
- 卷积在pytorch中有两种实现,一种是torch.nn.Conv2d(),一种是torch.nn.functional.conv2d(),
- 选择最实用来谈一下首先,你要慎重选择你就业的城市。这点是目前多数人都忽略的重要因素。无论你的设计思路和发展方向都要依托你所在城市来作为载体。
- Ajax类  
- 内容摘要: 当用户填写页面<FORM>内容时所提供的全部值,或在浏览器地址栏输入在URL后的值,通过Form和QueryStrin
- MySQL Group By用法我们现在回到函数上。记得我们用 SUM 这个指令来算出所有的 Sales (营业额)吧!如果我们的需求变成是
- 1、你需要通过指定的文本模式去检查字符串的开头或者结尾,比如文件名后缀,URL Scheme 等等。检 查 字 符 串 开 头 或 结 尾
- 前面已经介绍了关于Dreamweaver MX 2004的基本操作
- 区块链中的共识算法在比特币公链架构解析中,就曾提到过为了实现去中介化的设计,比特币设计了一套共识协议,并通过此协议来保证系统的稳定性和防攻击
- EXISTS该函数返回集合中第一个元素的索引,如果集合为空,返回NULLNULLNULLCollection.EXISTS(index)CO
- 本文介绍了网页运行代码框(runCode), 复制代码框(copyCode), 保存代码框(saveCode),的实现方法。javascri
- 代码如下:<%@LANGUAGE="VBSCRIPT" CODEPAGE="65001&quo
- 前言全可以访问相同的对象, 因此我们讲 这种变量名也叫对象的 "引用".验证1:a = 2b = 3print(id(a
- python刷CSDN访问量import requestsimport reimport timepayload = ""
- 从而达到方便快捷的目的,但是它在存储信息的时候往往会有一些敏感的东西,这些东西可能成为被攻击的目标,如银行的账号、信用卡事务或档案记录等。这