Python实现二分法算法实例
作者：junjie 发布时间：2021-06-23 19:31:12
标签：Python,二分法,算法
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);
注意：二分查找的前提必须待查找的序列有序。
0
投稿猜你喜欢
- 如下所示：device = torch.device("cuda:0" if torch.cuda.is_availab
昨晚收到客服MM电话，一用户反馈数据库响应非常慢，手机收到load异常报警，登上主机后发现大量sql执行非常慢，有的执行时间超过了10s优化- varchar(n)长度为 n 个字节的可变长度且非 Unicode 的字符数据。n 必须是一个介于 1 和 8,000 之间的数值。存储大
- 前言本系统是基于fabric.js实现的canvas版图片,文本编辑器,支持对图片的放大,缩小,旋转,镜面翻转,拖动,显示/隐藏图层,删除图
- var arr=['a','b','c'];若要删除其中的'b',有两种方法
- 误区 #12:TempDB的文件数和需要和CPU数目保持一致错误 哎，由于上述误区是微软“官方”的建议，
- 在MySQL中，A LEFT JOIN B join_condition执行过程如下：· 根据表A和A依赖的所有表设置表B。· 根据LEFT
- 解析来自各种来源和格式的时间序列信息pd.to_datetime( arg,#int, float, str, d
- 默认情况下Python的logging模块将日志打印到了标准输出中，且只显示了大于等于WARNING级别的日志，这说明默认的日志级别设置为W
- 本文实例讲述了Python创建xml的方法。分享给大家供大家参考。具体实现方法如下：from xml.dom.minidom import
- 本人之前写了一套基于unnitest框架的UI自动化框架，但是发现了pytest框架之后觉得unnitest太low，现在重头开始学pyte
- 如果你的数据量有几十万条，用户又搜索一些很通俗的词，然后要依次读最后几页重温旧梦。mysql该很悲壮的不停操作硬盘。 所以，可以试着让mys
- 本例子实现从hbase获取数据，并发送kafka。使用#!/usr/bin/env python#coding=utf-8import sy
- Golang连接Redis数据库golang连接数据库，这里博主推荐使用go-redis这个库，理由很简单（连接数据库的操作类似在数据库里面
- 背景借助django-admin，可以快速得到CRUD界面，但若需要创建多选标签字段时，需要对表单进行调整示例model.py一个tag（标
- 有很多时候，我们会在python的运行过程中得到一些重要的变量，比如一个数据量很庞大的dict。而且，后面的某些程序也会用到这个dict，那
- ECharts作为一个图标库已经被大家广泛使用，它提供了各式各样的图表类型，但是在我们日常使用中可能只会用到其中的某几个图表类型，常用的基本
- 前言技术能解决的事情改技术技术解决不了的事情该需求现状假设我们目前有两张表业务表 书（ t_a_book ） 阅读历史记录表 (t_r_bo
- 为什么需要虚拟DOM？如果对前端工作进行抽象的话，主要就是维护状态和更新视图，而更新视图和维护状态都需要DOM操作。其实近年来，前端的框架主
- 如下所示：import urllib.requestimport urllib.parseurl = 'https://weibo.
