[DS+Algo] 008 查找
2024-10-02 06:41:01
1. 常见搜索方法
- 顺序查找
- 最优时间复杂度:O(1)
- 最坏时间复杂度:O(n)
- 二分法
- 最优时间复杂度:O(1)
- 最坏时间复杂度:O(logn)
- 二叉树
- 若是“二叉搜索树”
- 最优时间复杂度:O(1)
- 最坏时间复杂度:O(logn)
- 若是“二叉搜索树”
- 哈希
- 时间复杂度:O(1)
2. 二分查找的代码实现
- 顺序查找,就是一个循环遍历
- BST,其实和二分换汤不换药
- 哈希,暂且按下不表
代码实现
from random import randrange
def binary_search_1(lst, item):
first = 0
last = len(lst) - 1
while first <= last:
mid = (first + last) // 2
if lst[mid] == item:
return True
elif item < lst[mid]:
last = mid - 1
else:
first = mid + 1
return False
def binary_search_2(lst, item):
n = len(lst)
if n == 0:
return False
mid = n // 2
if lst[mid] == item:
return True
elif item < lst[mid]:
return binary_search_2(lst[:mid], item)
else:
return binary_search_2(lst[mid+1:], item)
if __name__ == "__main__":
lst = [i+randrange(0, 5) for i in range(0, 100, 5)]
r_num = randrange(0, 100)
print("lst =", lst)
print(f"binary_search_1(lst, {r_num}):", binary_search_1(lst, r_num))
print(f"binary_search_2(lst, {r_num}):", binary_search_2(lst, r_num))
最新文章
- 论文阅读(Weilin Huang——【TIP2016】Text-Attentional Convolutional Neural Network for Scene Text Detection)
- 解决Firefox浏览器每次打开都弹出导入向导的问题
- 《算法竞赛入门经典》5.41数学基础-Cantor的数表
- javascript中的表结构
- jQuery.qrcode.js客户端生成二维码,支持中文并且可以生成LOGO
- laravel扩展图片处理Intervention Image
- Css3执行后显示最后一针
- In-Memory:内存优化数据的持久化和还原
- UISegmentedControl 踩坑
- MongoDB 分片集群搭建
- 20181218-PostgreSQL数据库Extension管理
- 【转载】ucos临界段
- Http/2知识图谱
- cad.net 利用win32api实现一个命令开关参照面板
- 一本通1530 Ant Trip
- 大白菜装机版一键制作启动u盘教程
- ios instancetype 和 id 的异同
- scala 的安装 与 IDEA安装使用
- 直接拿来用!最火的Android开源项目(转)
- WebAPI请求——js调用
热门文章
- Shiro(一)
- pyqt5--动画
- (转载)自然语言处理中的Attention Model:是什么及为什么
- 通俗理解vue路由的导航钩子中关于next()
- antd表格分页
- android出现backtrace 定位方法
- [luogu]P1800 software_NOI导刊2010提高(06)[DP][二分答案]
- docker安装xxl-job
- No &#39;Configuration&#39; method was found in class &#39;WebApp.Startup
- python实现RGB转换HSV