首页/新闻资讯/正文详情

C++二分和lower_bound,upper_bound

发布时间:2026/11/20 3:56:46 来源:云帆数科 栏目:资讯中心
C++二分和lower_bound,upper_bound
二分二分是一种高效的查找算法。当一个有序题目要求的序列a[n]以a[x]1xn为分界线分成两半a[1]~a[x]和a[x1]~a[n]其中一半满足某要求另一半不满足要求现在要求x或者x1的话就可以用到二分。这么说有点绕用一道模板例题来演示有一个长度为n的从大到小的序列a要求最小的大于q的数。思路如果不用二分可以从头往前遍历a找到第一个大于q的数为止这样在最坏情况下的时间复杂度是O(n)。O(logn)优化因为是有序序列那么前面有一段元素就会小于等于q然后从某个元素开始后面的元素就会大于q现在要求出这个分界线就可以所以可以用二分设置两个端点l1rn。l和r之间是可能为答案的元素定义mid(lr)÷2。判断a[mid]是否满足大于q ①如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid]我们要求最小的大于 q的数所以mid后面的数都不可能是答案mid可能是答案令rmid。 ②如果a[mid]小于等于q那么q之前的数都小于等于q所以mid和mid之前的的数都不可能是 答案就让lmid1。重复2、3步直到lr此时r就是答案。例子n6一个数列a:122356要求第一个大于3的数。设置l1r6。mid(16)/23(保留整数)。a[3]223不可能是答案所以让l314。mid(46)/25。a[5]553可能是答案所以让r5。mid(45)/23(保留整数)。a[4]333不可能是答案所以让l415。此时发现lr所以a[r]——5就是答案!模板程序#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int l1,rn; while(lr){//重复执行直到lr int mid(lr)/2;//求出mid if(a[mid]q)rmid; //如果a[mid]大于q就说明mid之后的数都大于q但是都大于等于a[mid] else lmid1; //如果a[mid]小于等于q那么q之前的数都小于等于q } couta[r];//a[r]就是答案 return 0; }样例输入61 2 2 3 5 63样例输出5另一个很重要的模板求第一个小于q的数#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int l1,rn; while(lr){//重复执行直到lr int mid(lr)/2;//求出mid if(a[mid]q)lmid; //如果a[mid]小于q就说明mid之前的数都小于q但是都大于等于a[mid] else rmid-1; //如果a[mid]大于等于q那么q之后的数都大于等于q } couta[l];//a[l]就是答案 return 0; }二分答案二分答案就是二分查找的复杂版要判断的条件复杂了刚才我们判断的条件都是a[mid]q或者a[mid]q但还是满足一段满足条件、另一段不满足条件这个时候我们一般写一个check(x)函数函数返回0、10表示不满足1表示满足。例求一个数的3次方等于q(保证这个在-100~100之间)精确到小数点后3位。这道题涉及到浮点数二分答案但和刚才同理。#includebits/stdc.h using namespace std; const double eps1E-6;//设置精度 int q; bool check(double x){ if(x*x*xq)return 1; else return 0; } int main(){ cinq; double l-100,r100; while(r-leps){//重复执行直到l与r的差小于精度 double mid(lr)/2;//求出mid if(check(mid))lmid; else rmid; } coutfixedsetprecision(3)r; return 0; }lower_bound和upper_bound:lower_bound和upper_bound是C自带的二分函数很好用对于有序递增数组a[1]~a[n]:lower_bound(a1an1q):用二分查找返回数组a第一个大于等于q的元素的迭代器。upperer_bound(a1an1q):用二分查找返回数组a第一个大于q的元素的迭代器。如果没找到就返回a[n1]的迭代器。想转换成下标-a就行时间复杂度O(logn)。例有一个长度为n的从大到小的序列a要求最小的大于等于和最小大于q的数:#includebits/stdc.h using namespace std; const int N1E610; int a[N]; int main(){ int n,q; cinn; for(int i1;in;i)cina[i]; cinq; int ans1lower_bound(a1,an1,q)-a;//迭代器-a int ans2upper_bound(a1,an1,q)-a;//迭代器-a couta[ans1]endla[ans2]; return 0; }以上是二分和lower_bound和upper_bound的一些基本知识。谢谢观看。

相关推荐

BP神经网络与PID控制融合的自适应优化方法
BP神经网络与PID控制融合的自适应优化方法

1. 项目概述:BP神经网络与PID控制的融合创新在工业控制领域,PID控制器因其结构简单、鲁棒性强等特点,长期占据主导地位。但传统PID控制器在面对非线性、时变系统时,固定参数往往导致控制性能下降。2018年某汽车厂喷涂机器人出现的… · 2026/11/19 14:20:56

MyBatis-Plus指南:从入门到面试
MyBatis-Plus指南:从入门到面试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 3:56:46

RAG 评测方法完整体系
RAG 评测方法完整体系

RAG 评测方法完整体系 RAG 评测不存在单一万能方法,而是一套分层解耦定位问题、多方法互补验证、基准对标量化、线上闭环迭代的方法体系,核心解决 RAG 「输出概率化、链路环节多、质量难量化、场景覆盖不全」的痛点。不同研发阶段、不同评测维度、不同风… · 2026/11/5 14:06:00

查询电工证的平台如何应对2026河南最新政策
查询电工证的平台如何应对2026河南最新政策

查询电工证的平台如何应对2026河南最新政策 之前考的证在外省能不能转过来?这是很多特种作业人员的共同疑问,尤其是在河南工作的你,可能已经听说了2026年河南最新政策对电工证的办理、复审、查询、转接等事项都有了新的要求。不管是从外地转过来的… · 2026/11/20 3:56:18

南京考电工证容易吗真实经历揭秘:实操考试心里没底怕挂科?别慌!
南京考电工证容易吗真实经历揭秘:实操考试心里没底怕挂科?别慌!

南京考电工证容易吗真实经历揭秘:实操考试心里没底怕挂科?别慌! 刚报名准备考电工证的你是不是也和我一样,心里直打鼓?实操考试到底难不难?能不能一次性通过?这些疑问天天在脑海里盘旋。我之前就是个典型的“小白”,抱着侥幸心理去考,结果实操环节差… · 2026/11/20 3:56:18

封丘电工证在哪里办怎么考?官方报名入口全攻略
封丘电工证在哪里办怎么考?官方报名入口全攻略

封丘电工证在哪里办怎么考?官方报名入口全攻略 之前考的证在外省能不能转过来?这几乎是所有准备报考或已经持有电工证的朋友最先关心的问题。尤其是像你这样已经在安阳从事市政公用工程工作的,可能会有跨省执业、换证、补办、复审等多种情况。别急,这篇文… · 2026/11/20 3:56:18

58岁适合考电工证吗官方回应来了,实操考试心里没底怕挂科别慌
58岁适合考电工证吗官方回应来了,实操考试心里没底怕挂科别慌

58岁适合考电工证吗官方回应来了,实操考试心里没底怕挂科别慌 你是不是也这样,40多岁了还在琢磨要不要考个电工证?有人说年龄大了学不会,实操考试心里没底怕挂科,还有人担心58岁了还能不能拿到证?别急,官方回应来了,咱们一起来看看真相到底如何… · 2026/11/20 3:56:18

工地太忙根本没时间复习考试?萍乡考电工证需要什么良心建议
工地太忙根本没时间复习考试?萍乡考电工证需要什么良心建议

工地太忙根本没时间复习考试?萍乡考电工证需要什么良心建议 你是不是也这样?每天在工地忙得脚不沾地,想考个电工证,但又担心自己没时间复习、没精力准备?别急,这正是我今天想跟你说的—— 萍乡考电工证需要什么 ,我来给你讲清楚,也给个 良心建议… · 2026/11/20 3:56:18

衢州电工证办理良心建议:怕考不过白交培训费?先看这篇避坑指南
衢州电工证办理良心建议:怕考不过白交培训费?先看这篇避坑指南

衢州电工证办理良心建议:怕考不过白交培训费?先看这篇避坑指南 怕考不过白交培训费?衢州电工证办理真的有那么难?别急,这些建议能帮你少走弯路。作为一名在应急管理领域摸爬滚打了十年的老手,我见过太多人因为不了解流程、备考方法错误,最后钱花了还拿… · 2026/11/20 3:55:18

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/19 16:06:02

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/19 17:40:37

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/19 17:50:07

建设厅特种工周三报名怎么弄?上岗必备别被中介坑
建设厅特种工周三报名怎么弄?上岗必备别被中介坑

建设厅特种工周三报名怎么弄?上岗必备别被中介坑 不知道去哪报名怕被中介坑?作为商丘某高校工程类应届毕业生,小李最近就遇到了这样的困扰。他刚毕业,正在找实习岗位,发现很多工地都要求持有特种作业操作证,尤其是【建设厅特种工周三报名】这个时间点,… · 2026/11/20 0:00:54

中专考的中级电工证内部消息全攻略
中专考的中级电工证内部消息全攻略

中专考的中级电工证内部消息全攻略 你中专毕业,手头有中级电工证,但不知道从哪开始报名,怕被中介坑?别急,这篇文章就是为你量身定制的“内部消息”,帮你避开报名陷阱,稳稳拿到证书。… · 2026/11/20 0:00:54

外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价
外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价

外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价 之前考的证在外省能不能转过来?这几乎是所有在外地打拼的电工从业者最关心的问题。特别是像洛阳这样的工业城市,很多电工证是在外地考的,现在想在当地用,流程是不是很复杂?其实,只要搞清楚… · 2026/11/20 0:00:54

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:25

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:32

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码