Python实现二分法算法实例
作者:junjie 时间:2021-06-23 19:31:12
1.算法:(设查找的数组期间为array[low, high])
(1)确定该期间的中间位置K
(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:
a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]
b.array[k]<T 类似上面查找区间为array[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间缩小一半。递归找,即可。
#!/usr/bin/python
# -*- coding: utf-8 -*-
def BinarySearch(array,t):
low = 0
height = len(array)-1
while low <= height:
mid = (low+height)/2
if array[mid] < t:
low = mid + 1
elif array[mid] > t:
height = mid - 1
else:
return array[mid]
return -1
if __name__ == "__main__":
print BinarySearch([1,2,3,34,56,57,78,87],57)
结果:57
3.时间复杂度:O(log2n);
注意:二分查找的前提必须待查找的序列有序。
标签:Python,二分法,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
使用pandas实现csv/excel sheet互相转换的方法
2022-05-22 18:38:18
python图形界面tkinter的使用技巧
2022-04-24 01:34:22
![](https://img.aspxhome.com/file/2023/5/85195_0s.png)
理解Python垃圾回收机制
2023-01-19 23:39:32
python二分法查找算法实现方法【递归与非递归】
2023-04-17 08:13:47
python实现凯撒密码、凯撒加解密算法
2023-08-27 17:49:22
Python + Requests + Unittest接口自动化测试实例分析
2021-08-08 05:41:47
![](https://img.aspxhome.com/file/2023/2/65122_0s.png)
Python编写带选项的命令行程序方法
2023-11-18 20:47:35
Python自动创建Excel并获取内容
2023-12-31 01:42:07
![](https://img.aspxhome.com/file/2023/4/109574_0s.png)
解析Python扩展模块的加速方案
2022-12-26 04:53:00
![](https://img.aspxhome.com/file/2023/0/128720_0s.png)
详解Python 2.6 升级至 Python 2.7 的实践心得
2022-01-03 09:47:09
为什么Access数据库的精髓不在VBA之中
2008-11-28 16:45:00
Python实现快速排序的方法详解
2022-08-29 13:08:35
基于Python实现抢注大词的提词工具
2022-04-07 02:00:20
![](https://img.aspxhome.com/file/2023/8/133448_0s.png)
dataframe设置两个条件取值的实例
2021-09-15 05:56:50
python绘制圆柱体的方法
2022-07-31 02:00:31
![](https://img.aspxhome.com/file/2023/6/96946_0s.jpg)
python实现简单倒计时功能
2022-09-29 03:08:32
![](https://img.aspxhome.com/file/2023/5/75905_0s.jpg)
提醒各位一下,IE透明会失效的
2009-03-31 12:48:00
![](https://img.aspxhome.com/file/UploadPic/20093/31/icon_lol-37s.gif)
简单介绍Python中的RSS处理
2023-03-03 13:59:17
详解python3 + Scrapy爬虫学习之创建项目
2022-07-22 18:02:05
![](https://img.aspxhome.com/file/2023/2/109592_0s.png)
python中pytest收集用例规则与运行指定用例详解
2021-12-01 14:23:21