数据结构与算法之二分查找法的总结
2021/11/12 22:41:33
本文主要是介绍数据结构与算法之二分查找法的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分查找也叫做折半查找。二分查找的条件:①是一个有序序列 ②是一个顺序表。
比如有序的列表:[1,2,3,5,6,7,8,9]
二分查找的复杂度:
最优复杂度:O(1)
最坏复杂度:O(logn)
算法思想:
给定一个序列,查找序列中是否有元素a,查找的方法是:将序列折半,找到中间位置的数值mid,将该数值和a进行比较,比a大,则在左边的序列中找a是否存在,方法还是折半查找,如果mid比a小,那么在中间值右边中的序列中找a是否存在,方法也还是折半查找。可以看到上面有部分重复的功能,就是折半查找,这块可以使用递归,也可以不使用递归。下面会给出两个例子分别介绍这两种方法:
例1:递归实现:
def binary_find(alist,item): n = len(alist) #递归结束条件 if n == 0: return False mid = n//2 if alist[mid] == item: return True elif alist[mid] > item: return binary_find(alist[:mid],item) else: return binary_find(alist[mid+1:],item) l = [1,2,9,34,999] re = binary_find(l,22) print(re) re = binary_find(l,999) print(re)
运行结果:
False True
例2:非递归实现
def binary_find2(alist,item): n = len(alist) start = 0 end = n-1 while start <= end: #这里要注意等于不能少 mid = (end + start)//2 if alist[mid] == item: return True elif alist[mid] > item: end = mid - 1 else: start = mid + 1 return False l = [1,2,9,34,999] re = binary_find2(l,22) print(re) re = binary_find2(l,999) print(re)
运行结果:
False True
复杂度分析:
可以看到上面的最优的复杂度就是正好中间的mid值就是我们要查找的值,复杂度为O(1),最坏复杂度就是:logn
其实如果不用二分法查找,使用for循环也是可以的,但是如果数据很大,那么查找速度很慢,for循环查找的最优复杂度为O(1),最坏复杂度为O(n),而我们的二分法查找最坏复杂度是O(logn),所以可以看到复杂度有所降低。
这篇关于数据结构与算法之二分查找法的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署