python有序查找算法 二分法实例解析
作者:TTyb 时间:2023-04-15 07:55:36
这篇文章主要介绍了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
标签:python,查找,算法,二分
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python可视化神器pyecharts绘制漏斗图
2023-01-09 08:40:09
![](https://img.aspxhome.com/file/2023/2/100962_0s.png)
Python:二维列表下标互换方式(矩阵转置)
2022-07-09 13:29:58
laravel清除视图缓存的代码
2023-11-24 14:39:39
如何将Python编译成C语言
2022-01-02 10:49:31
![](https://img.aspxhome.com/file/2023/4/105414_0s.png)
解决SQL Server的“此数据库没有有效所有者”问题
2024-01-16 22:21:58
解读sql中timestamp和datetime之间的转换
2024-01-26 18:59:14
![](https://img.aspxhome.com/file/2023/8/128008_0s.png)
Mac上安装MySQL过程分享
2024-01-22 16:03:34
Python实现分割文件及合并文件的方法
2022-01-28 00:02:02
使用Pyhton 分析酒店针孔摄像头
2022-04-16 18:59:24
![](https://img.aspxhome.com/file/2023/0/125200_0s.jpg)
Python lambda表达式原理及用法解析
2021-03-02 18:52:12
Perl字符串处理函数大全
2023-11-25 17:33:35
MySQL 序列 AUTO_INCREMENT详解及实例代码
2024-01-20 17:04:37
Python脚本实现自动将数据库备份到 Dropbox
2024-01-20 09:56:45
JavaScript中实现字符串的取左取右(实现left和right功能)
2009-07-20 12:39:00
Python中json.dumps()函数的使用解析
2022-11-04 19:41:09
Python中创建二维数组
2023-11-24 15:14:54
![](https://img.aspxhome.com/file/2023/8/131508_0s.png)
解决Pycharm调用Turtle时 窗口一闪而过的问题
2023-05-06 14:46:29
![](https://img.aspxhome.com/file/2023/2/124242_0s.jpg)
导航设计与信息架构
2008-01-13 22:08:00
GDAL 矢量属性数据修改方式(python)
2021-01-30 20:53:28
![](https://img.aspxhome.com/file/2023/7/78537_0s.jpg)
python 实现人和电脑猜拳的示例代码
2021-04-11 01:42:14