Python有序查找算法之二分法实例分析
作者:叮了咣当 时间:2023-04-09 00:02:37
本文实例讲述了Python有序查找算法之二分法。分享给大家供大家参考,具体如下:
二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...
例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况:
① 假如arr[center]>key,说明key在arr中心左边范围;
② 假如arr[center]<key,说明key在arr中心右边范围;
③ 假如arr[center]=key,说明key在arr中心。
范围每次缩小一半,写个while的死循环知道找到为止。
二分法查找非常快且非常常用,但是唯一要求是要求数组是有序的
前面一篇冒泡排序可以去看看:
https://www.jb51.net/article/130288.htm
二分法的代码如下:
# -*- 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__":
print("脚本之家测试结果:")
arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
while True:
key = raw_input("请输入你要查找的数字:")
if key == " ":
print("谢谢使用!")
break
else:
BinarySearch(arr, int(key))
运行结果:
希望本文所述对大家Python程序设计有所帮助。
来源:https://www.cnblogs.com/bfyin/p/6404173.html
标签:Python,二分法,查找算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
使用Python实现画一个中国地图
2023-10-01 00:39:36
![](https://img.aspxhome.com/file/2023/0/131140_0s.jpg)
Python实现的最近最少使用算法
2022-07-10 22:48:27
为什么MySQL选择Repeatable Read作为默认隔离级别
2024-01-13 01:09:26
![](https://img.aspxhome.com/file/2023/6/122936_0s.jpg)
如何解决客户机页面刷新时连接不上数据库问题?
2009-12-16 18:24:00
几行代码让 Python 函数执行快 30 倍
2021-06-22 14:52:23
![](https://img.aspxhome.com/file/2023/5/128645_0s.png)
八个有用的WordPress的SQL语句
2009-01-12 18:54:00
Python button选取本地图片并显示的实例
2023-10-06 15:56:32
Ajax+PHP边学边练 之五 图片处理
2023-11-18 07:21:29
![](https://img.aspxhome.com/file/2023/7/102087_0s.png)
基于Python实现原创程序猿乘风破浪小游戏
2021-03-09 01:41:51
![](https://img.aspxhome.com/file/2023/0/106970_0s.png)
Python 栈实现的几种方式及优劣详解
2023-11-02 14:25:18
![](https://img.aspxhome.com/file/2023/3/62623_0s.jpg)
python time()的实例用法
2022-01-09 02:33:02
利用OBJECT_DEFINITION函数来代码存档
2009-01-20 15:34:00
Python实现FTP文件定时自动下载的步骤
2022-04-13 02:07:14
php中如何判断一个网页请求是ajax请求还是普通请求
2023-10-13 14:42:30
实例学习call、apply、callee用法
2009-03-27 17:56:00
python多进程下的生产者和消费者模型
2022-05-30 02:37:07
![](https://img.aspxhome.com/file/2023/7/65847_0s.png)
python traceback捕获并打印异常的方法
2022-11-06 10:35:30
asp 类型转换函数大全第1/2页
2011-04-07 11:06:00
详解Python中range()与xrange()的区别
2021-09-06 12:32:14
小白入门篇使用Python搭建点击率预估模型
2021-02-09 20:49:04
![](https://img.aspxhome.com/file/2023/6/128496_0s.png)