python二分查找的原理
2023-09-11 14:18:27 时间
python二分查找的原理
原理
1、假设表中的要素按升序排列,将表中间位置记录的关键词与检索关键词进行比较,如果两者相等,则检索成功。
2、否则,利用中间位置记录将表分为前后两个子表。
如果中间位置记录的关键词大于搜索关键词,则进一步搜索前一个子表,否则进一步搜索后一个子表。重复以上流程,找到符合条件的记录,使检索成功,或者在子表不存在之前,此时检索不成功。
实例
JavaScript
"""
应用前提:在一个含有n个元素的有序序列中定位目标值 时间复杂度:O(logn)
该算法维持两个参数low和high,这样可使所有候选条目的索引位于low和high之间。首先, low=0和high=n-1。然后我们比较目标值和中间值候选项,即索引项[mid]的数据。
mid =L(low + high)/2 ]考虑以下三种情况:
- 如果目标值等于[mid]的数据, 然后找到正在寻找的值,则查找成功并且终止。
- 如果目标值< [mid] 的数据, 对前半部分序列重复这一过程,即索引的范围从low到mid-1.
- 如果目标值> [mid] 的数据,对后半部分序列重复这一过程,即索的范围从mid+1到high。
- 如果low >high,说明索引范围[low, high]为空,则查找不成功。该算法被称为二分查找
"""
def binary_search(alist, item):
"""非递归"""
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
mid = (first + last) // 2
if alist[mid] == item:
found = True
else:
if item < alist[mid]:
last = mid - 1
else:
first = mid + 1
return found
def binary_search_recursion(alist, item):
if len(alist) > 0:
mid = len(alist) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search_recursion(alist[:mid], item)
else:
return binary_search_recursion(alist[mid + 1:], item)
return False
if __name__ == '__main__':
ret = binary_search_recursion([17, 20, 26, 31, 44, 54, 55, 65, 77, 69], 26)
print(ret)
ret = binary_search([17, 20, 26, 31, 44, 54, 55, 65, 77, 69], 68)
print(ret)
以上就是python二分查找的原理,希望对大家有所帮助。更多Python学习指路:python基础教程
相关文章
- Python 爬虫 实例项目 大全
- Python中python-nmap模块的使用
- Python中pip安装报错Unable to create process using '....'
- Python+NumPy绘制常见曲线的方法详解_python
- Python的namedtuple使用详解
- Python kafka操作实例(kafka-python)
- 【华为OD机试真题 python】热点网站统计 【2022 Q4 | 200分】
- 超全Python学习路线图+14张思维导图,让python初学者不走弯路
- gyp ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- python入门常用方法(转json,模拟浏览器请求头,写入文件)
- 【python】+704个常用工具Python库
- python学习之OpenCV-Python模块的部分应用示例(生成素描图和动漫图)
- python LEGB原理简要介绍
- OpenCV Python – 如何对图像执行按位 NOT 操作?
- Python高级架构模式的整理
- 使用 PyWeb3D 的 3D 家具显示,用 Python 语法探索 three.js(教程含源码)
- (数据科学学习手札24)逻辑回归分类器原理详解&Python与R实现
- 【Python 八股文】- Nginx基础
- 【Python分布式服务框架】Docker部署Postgresql主从复制模式
- Python用python-docx读写word文档
- Selenium Python相关
- 【python养成】:案例练习(判断闰年、删除奇数、偶数降序排序、因式分解、100以内奇数之和、1234组成的素数、分段函数计算、100以内的所有丑数)
- 学习笔记(11):Python网络编程&并发编程-粘包底层原理分析
- 【python】list获取两个等长列表中同索引对应最大值的集合
- 每天学习亿点点-和python爬虫的第一次见面