二分查找(非递归、递归)python实现
2023-06-13 09:12:08 时间
# -*- coding: utf-8 -*-
"""
@author: sato
@file: binary_search.py
@time: 2019-09-03 15:21
"""
def binary_search(array, key):
"""二分查找非递归"""
if len(array) <= 1:
if array[0] != key:
return
start = 0
end = len(array) - 1
while start <= end:
mid = (end + start) // 2
if key < array[mid]:
end = mid - 1
elif key > array[mid]:
start = mid + 1
else:
return True
def binary_search(a, b):
"""非递归"""
min = 0
max = len(a) - 1
if b in a:
while True:
centre = int((max + min) / 2)
if a[centre] > b:
max = centre - 1
elif a[centre] < b:
min = centre + 1
elif a[centre] == b:
return centre
else:
return 'b in not in a'
def binary_search_reduce(array, key):
"""二分查找,递归实现版本"""
if len(array) == 0:
return False
mid = len(array) // 2
if array[mid] == key:
return True
elif key < array[mid]:
return binary_search_reduce(array[:mid], key)
else:
return binary_search_reduce(array[mid + 1:], key)
if __name__ == '__main__':
# 二分查找的最优时间复杂度为O(1),最坏时间复杂度为O(log n)
# 递归空间复杂度是:O(N) 非递归: O(1)
# 使用场景: 在有序数组中寻找指定元素
sorted_list = [1, 4, 5, 7, 8, 9, 10, 13, 15, 17, 19, 23, 35]
assert binary_search(sorted_list, 1)
assert binary_search(sorted_list, 10)
assert binary_search(sorted_list, 35)
assert binary_search_reduce(sorted_list, 1)
assert binary_search_reduce(sorted_list, 13)
assert binary_search_reduce(sorted_list, 35)
相关文章
- 用python实现线性回归算法
- 二级Python选择题_二级python选择题题库
- pycharm pro 2021 mac中文永久试用版(Python编辑开发)
- python十进制转换_Python 进制转换
- Python 递归函数
- python监控网页内容变化_使用Python监控文件内容变化代码实例
- python表情代码_Python实现表情包的代码实例[通俗易懂]
- 【python】之哥德巴赫猜想(递归法)和教室排课(枚举法)
- 【说站】python字典如何进行运算
- 遗传算法的应用实例python实现_遗传算法Python解决一个问题
- Python的特点是什么_python具有的特点
- 用递归实现斐波那契数列 python_python斐波那契数列前30项
- python抛出异常和捕获异常_Python异常
- python上的表白代码_用Python实现表白代码
- python hexdump_笨办法学 Python · 续 练习 26:`hexdump`
- python做微信回复机器人_Python自动化脚本
- Python递归实现汉诺塔详解编程语言
- 小白的Python之路 day5 python模块详解及import本质编程语言
- Python学习:1.快速搭建python环境详解编程语言
- 开发Linux下Python编程:实现自己的开发梦想(linux下python)
- Linux查看Python版本的有效方法(linux查看python版本)
- Linux环境下Python开发的历程(linux与python)
- MySQL与Python的协同运行:一种全新的开发体验(mysql与python)
- Linux 下 Python 升级:轻松完成升级操作(linux下升级python)