python中二分查找法的实现方法
作者:宋宋大人 时间:2023-02-02 16:19:16
如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写对,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。
1、二分查找
在一个有序并且无重复的列表中,对该列表的元素进行查找。
2、特点
(1)必须针对于有序列表
(2)该列表必须无重复
(3)按下标索引查找
3、使用方法
非递归实现:
def binary_search(alist, item):
"""二分查找 非递归方式"""
n = len(alist)
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
end = mid - 1
else:
start = mid + 1
return False
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))
递归实现:
def binary_search_2(alist, item):
"""二分查找 递归方式"""
n = len(alist)
if 0 == n:
return False
mid = n // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search_2(alist[:mid], item)
else:
return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))
基础知识点扩展:
介绍
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
前提
必须待查找的序列有序
时间复杂度
O(log2n)
原理
1)确定该期间的中间位置K
2)将查找的值t与array[k]比较,若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。
3)区域确定过程:
若array[k]>t,由于数组有序,所以array[k,k+1,……,high]>t;故新的区间为array[low, ..., K-1];
反之,若array[k]<t对应查找区间为array[k+1, ..., high]
来源:https://www.py.cn/jishu/jichu/21634.html
标签:python,二分查找
0
投稿
猜你喜欢
Mysql InnoDB引擎中的数据页结构详解
2024-01-16 20:51:29
使用python实现对元素的长截图功能
2023-11-20 10:27:44
Python中统计函数运行耗时的方法
2023-03-11 02:17:25
vue中将html字符串转换成html后遇到的问题小结
2024-04-30 10:22:02
Python可视化库之HoloViews的使用教程
2023-11-05 17:09:03
Oracle查看逻辑读、物理读资源占用排行的SQL语句
2023-06-25 23:53:53
javascript 选择文件夹对话框(web)
2024-04-17 09:48:43
深入理解Tensorflow中的masking和padding
2022-01-26 02:21:44
事件检测
2009-04-11 18:03:00
使用python制作一个解压缩软件
2023-04-27 19:08:37
Python列表解析配合if else的方法
2021-10-08 06:50:11
如何利用Python实现简单C++程序范围分析
2022-07-19 00:32:48
python开发利器之ulipad的使用实践
2021-07-25 00:55:17
jupyter notebook如何使用matlab
2022-11-08 18:17:51
python学习入门细节知识点
2022-09-07 06:40:53
python创建线程示例
2021-07-21 00:20:37
使用Python处理json字符串中的非法双引号问题
2021-01-19 19:26:13
asp如何写入超长的字符串?
2010-06-09 18:53:00
在IE下用getAttribute时要小心
2008-08-21 12:54:00
Python Web框架Flask信号机制(signals)介绍
2022-12-01 13:52:23