【二分查找法及其应用】
文章目录
- 一. 前提
- 二. 基本思路
- 三. 代码实现
- 四. 封装在STL中的二分查找算法
- 五. 浮点数二分
一. 前提
- 待查找的序列是有序的;
- 待查找的 a 采取顺序存储结构。
二. 基本思路
设在升序序列 a [ low…high ] 查找的 k ,
首先找中间值 mid= a [ ( low+high )/2 ] ;
然后比较 k 和 a [ mid ] , 分成三个情况:
(1)k == a[ mid ] , 直接返回 a [ mid ] ;
(2)k < a [ mid ] , 新的查找区域变为左子表 a [ low , mid-1 ] ;
(3)k > a [ mid ] , 新的查找区域变为右子表 a [ mid+1 , high ] ;
下一次查找根据 新的查找区间 进行查找。
三. 代码实现
//二分查找法
int BinSearch(int a[],int low,int high,int k)
{if(low<=high){ //当前区间存在元素 int mid=(low+high)/2;if(a[mid]==k)return mid; //找到后返回其下标 if(a[mid]<k)return BinSearch(int a[],int low,int mid-1,int k);if(a[mid]>k)return BinSearch(int a[],int mid+1,int high,int k);}else{return -1; //区间不存在元素,返回 -1 }
}
可见二分查找的时间重要花费在元素比较上,其时间复杂度为O(log2n\log_{2}nlog2n)
四. 封装在STL中的二分查找算法
- lower_bound
ForwoardIterator lower_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
- upper_bound
ForwoardIterator upper_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
- binary_search
bool binary_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
区间中存在要查找的值,返回 true ;否则, false
五. 浮点数二分
1.求n的平方根,保留6位小数
#include<bits/stdc++.h>
using namespace std;int main()
{double n;cin>>n;double l=0,r=n;while(r-l>=1e-8){ //负的,别忘!!!double mid=(l+r)/2;if(mid*mid>n) r=mid;else l=mid;}printf("%lf",l);return 0;}
相关文章:
【二分查找法及其应用】
文章目录一. 前提二. 基本思路三. 代码实现四. 封装在STL中的二分查找算法五. 浮点数二分一. 前提 待查找的序列是有序的;待查找的 a 采取顺序存储结构。 二. 基本思路 设在升序序列 a [ low…high ] 查找的 k , 首先找中间值 mid a [ ( lowhigh )/2 …...
Android 进阶——Framework核心 之Binder Java成员类详解(三)
文章大纲引言一、Binder Java家族核心成员关系图二、Binder Java家族核心成员源码概述1、android.os.IBinder1.1、boolean transact(int code, Parcel data, Parcel reply, int flags) send a call to an IBinder object1.2、String getInterfaceDescriptor()1.3、boolean ping…...
Maven
Maven 1.什么是Maven 官方网站 https://maven.apache.org/ Maven是一款服务于Java平台的自动化构建工具,它可以帮助我们更方便的对项目进行构建、管理项目jar包 ,包括: bulid 项目,切换 jar 版本,添加 jar, 删除 jar 包等 1.…...
1947抓住那头牛(队列 广度优先搜索)
目录 题目描述 解析 解题思路 代码部分 代码部分 运行结果 看看len数组中各个位置的标记值 为什么这样做一定是最短路径: 题目描述 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<N<100000)&…...
基于linux5.15.5的IMX 参考手册 ---21
基于linux5.15.5的IMX 参考手册 — 21 10.5.2高清多媒体接口(HDMI)和显示端口(DP)概述 10.5.2.1测试名称 •mxc_cec_test.out 10.5.2.1.1位置 /unit_tests/HDMI/ 10.5.2.1.2功能 验证HDMI CEC功能并向HDMI接收器发送断电命令。 1…...
Android Dalvik虚拟机 堆初始化流程
前言 上篇文章介绍了dalvik虚拟机启动流程,在dalvik虚拟机启动时调用了dvmGcStartup来启动堆。 本文介绍我们在日常开发使用Java时的堆创建流程。 Dalvik堆介绍 Dalvik虚拟机中,堆是由heap[0] Active堆和heap[1] Zygote堆两部分组成的。其中ÿ…...
0讲(补)——开发前必备基本常识
前言 专栏内容持续补充更新,目前正在进行优惠活动 目录 前言 一、函数的声明和定义 二、预编译 三、串口打印中的printf函数的使用...
JS学习笔记
1.WebAPIs简介导读Web APIs 和JS 基础关联性JS 基础阶段以及 Web APIs 阶段JS基础学习 ECMAScript 基础语法为后面作铺垫,Web APIs 是JS 的应用,大量使用JS基础语法做交互效果①JS 基础阶段我们学习的是ECMAScript 标准规定的基本语法要求同学们掌握JS 基…...
linux005之用户、组管理
linux用户管理简介: 任何使用linux系统的用户,都必须使用一个合法的账号和密码,账号和密码一般都是超级管理员创建,当然普通用户也可以创建用户,前提是必须拥有创建用户权限。 root是linux系统中默认创建的超级用户 创…...
列线图工具_Nomogram
定义 列线图是一种相对传统的分析方法,用于展示自变量和因变量的线性关系,及其特征的重要程度。 现在用SHAP,和机器学习库中的 Feature importance 工具可以实现类似甚至更好效果。不过很多传统的研究领域比较认这种方法。 列线图工具建立在…...
【C++】类和对象(一)
目录一、面向过程和面向对象初步认识二、类的引入三、类的定义四、类的访问限定符及封装4.1、访问限定符4.2、封装五、类的作用域六、类的实例化七、类对象的大小八、this指针8.1、this指针的引出8.2、this指针的特性8.3、C语言和C实现Stack的对比一、面向过程和面向对象初步认…...
Python获取搜索引擎结果
前言 想快速获取各个高校的博士招生网站,于是通过python先获取出有可能包含高校博士招生网站的URL,然后通过人为筛选得到了想要的招生网站(注意,并非直接爬取,是间接获取的)。 整理了一份网站名单&#x…...
2.4.8 PCIe——物理逻辑层——REFCLK
一、概述 pcie的参考时钟由板级输入,提供给IP内PHY层的PLL使用,由PLL产生core_clk和pipe_clk。 二、REFCLK产生方式 Serdes 所用时钟由 PHY 模块内的PLL生成,PLL的参考时钟可以由common clock(外部背板提供)、separ…...
树莓派4B arm64 搭建 docker+drone+gitea
树莓派4B arm64 搭建 dockerdronegitea 记录时间: 2023年02月10日 树莓派烧录 如何用树莓派搭建一台永久运行的个人服务器? https://mp.weixin.qq.com/s?__bizMzI5NjA0ODkwNA&mid2651847658&idx1&sn267a1257b43d4a76f2a081ed157b77f9&chksmf7b11…...
Java的JDBC编程
目录 1. 打开IDEA,新建Project 2. 引入依赖 (1)下载驱动包 (2)将驱动包导入Project 3. 编写代码 (1)创建数据源 (2)让代码和数据库服务器建立联系 (3&…...
CSS:块格式化上下文(BFC)
块格式化上下文是块级盒子的布局过程发生的区域,也是浮动元素与其他元素交互的区域。 块格式化上下文(BFC)的创建 满足以下条件将创建块格式化上下文: 根元素()浮动元素(float 值不为 none)绝对定位元素…...
paddle表情识别部署
表情识别模块1.环境部署1.1同样采用fastDeploy库1.2相关模型2.封装成静态库2.1参考[百度Paddle中PP-Mattingv2的部署并将之封装并调用一个C静态库](https://blog.csdn.net/weixin_43564060/article/details/128882099)2.2项目依赖添加2.3生成成功3.test3.1创建emotion_test项目…...
Python-第五天 Python函数
Python-第五天 Python函数一、函数介绍1. 什么事函数二、函数的定义1.函数的定义:2.案例三、函数的参数1.函数的传入参数2.案例升级四、函数的返回值1.什么是返回值2.返回值的语法3.None类型4.None类型的应用场景五、函数说明文档1.函数的说明文档2.在PyCharm中查看…...
【Python学习笔记】28.Python3 错误和异常
前言 作为 Python 初学者,在刚学习 Python 编程时,经常会看到一些报错信息,在前面我们没有提及,这章节我们会专门介绍。 Python3 错误和异常 Python 有两种错误很容易辨认:语法错误和异常。 Python assert…...
SQLServer 迁移到 MySQL 工具对比
我之所以会写这篇对比文章,是因为公司新产品研发真实经历过这个痛苦过程(传统基于 SQL Server开发的C/S 产品转为 MySQL云产品)。首次需要数据转换是测试环节,当时为了快速验证新研发云产品性能与结果准确性(算法类&am…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
