二分算法是经常使用的算法之一,熟练使用二分算法是一个程序员的基本素养。C++的<algorithm>头文件中存在lower_bound()
和upper_bound()
函数,支持在已排好序的容器中查找首个大于等于或者大于目标元素的迭代器位置。同时在有序容器类,例如set<>和map<>,也存在类似功能的函数。熟练使用lower_bound()
和upper_bound()
函数可以方便地使用二分算法解决问题。本文基于< algorithm>源代码,对lower_bound()
和upper_bound()
代码进行分析解释,对于实现严谨高效的二分算法具有重要参考价值。
本文在第二部分给出<algorithm>头文件中lower_bound()
和upper_bound()
函数的代码,并对代码进行分析解释;第三部分是对二分算法的实现,并注明了实现中需要注意的事项;最后一部分是本文参考文章链接。
lower_bound(first, last, value)
函数根据给定的value值,返回[first, last)范围中第一个大于等于value的迭代器(元素位置)。若无法找到,则返回last,因此实际可供返回的范围为[first,last]。
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;// 用于表示[first, last)的中间位置值
// count 表示待搜索的容器中元素个数,初始为last-first
// step 用来得到待搜索范围的中间位置
typename std::iterator_traits<ForwardIt>::difference_type count, step;
// distance即计算[first,last)中间的元素个数
count = std::distance(first, last);
// 若待搜索的容器中元素个数大于0个,则进入while循环
while (count > 0) {
it = first; // (1)
step = count / 2;// (2) 求中间位置元素距离first的间隔
std::advance(it, step); // (3),这三行用来使it等于[first,last)的中间位置。
// 例如:若待搜索的容器为{0,1,2,3},那么first指向元素0的位置,last指向3后面的一个位置,count为容器中元素的个数等于4,it指向0+4/2=2,即it指向2;
// 若待搜索的容器为{0,1,2},那么first指向元素0的位置,last指向3后面的一个位置,count为容器中元素的个数等于3,it指向0+3/2=1,即it指向1;
// 即若容器中元素个数为奇数,it指向中间位置的元素;若容器中个数为偶数,则it指向中间两个元素中后一个元素。
if (*it < value) {
// 若中间元素it小于value,则说明最终需要返回的元素在[it+1,last)范围内
first = ++it; //则将first赋值为it+1位置处
count -= step + 1; // 更新现在的搜索范围内的元素个数。count变为count - [first,it]范围内的元素个数,即count -= (step+1)
}
else
// 若中间元素it大于等于value,则说明最终需要返回的元素在[first,it]
// 因此此时不需要更改first位置,只需要令搜索范围变为[first,it),即count变为step即可;
// 此处新的搜索范围变为[first,it)而不是[first,it]的原因是,若[first,it)范围内找不到大于等于value的元素,则返回[first,it)范围内最后一个元素(it-1)的下一个元素位置(it)正好可以得到[first,last)范围内第一个大于等于value的位置。
// 同时,这样设置保证了每次循环的count值都变小。若初始容器为{10,10},value = 5,那么若此处更新使用count=step+1,则会形成死循环。
count = step;
}
// 返回结果第一个大于等于value的元素位置,若没有则first会指向last,即返回last。
return first;
}
可以将lower_bound()
函数理解为一个递归函数,该函数用于求在范围[first, first+count)范围内第一个大于等于value的元素,若不存在返回first+cound,只不过是使用while循环实现。在具体实现中保证了count每次循环都变为原来的一半,因此算法复杂度为log(n)。
upper_bound()
函数与lower_bound()
函数类似,只不过将判断条件if (*it < value)
变为if (!(value < *it))
,其他部分都相同,因此对upper_bound()
函数不在添加注释。
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0) {
it = first;
step = count / 2;
std::advance(it, step);
if (!(value < *it)) {
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}
基于第二部分中给出的代码,我们参考其代码结构给出二分算法的实现。
算法需要解决的问题为,给出一个递增数组nums
,求数组中第一个大于等于value的值的下标,若不存在则输出“不存在”。
实现代码如下:
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> nums = {
0,1,2,3,4,5,6,7,8,9};
int value = 5;
int first = 0;
int last = nums.size();
int step;
int count = last-first;
int middle;
while(count>0){
step = count/2;
middle = first+step;
if(nums[middle]<value){
first = middle+1;
count = count - (step+1);
}else{
count = step;
}
}
if(first<nums.size()){
cout<<"第一个大于等于"<<value<<"的元素下标为:"<<first<<endl;
}else{
cout<<"数组nums中没有大于等于"<<value<<"的元素"<<endl;
}
return 0;
}
程序输出为:
第一个大于等于5的元素下标为:5
lower_bound(first, last, cmp)
函数自定义比较函数。[1]. std::lower_bound
[2]. std::upper_bound
文章浏览阅读3.2k次。本文研究全球与中国市场分布式光纤传感器的发展现状及未来发展趋势,分别从生产和消费的角度分析分布式光纤传感器的主要生产地区、主要消费地区以及主要的生产商。重点分析全球与中国市场的主要厂商产品特点、产品规格、不同规格产品的价格、产量、产值及全球和中国市场主要生产商的市场份额。主要生产商包括:FISO TechnologiesBrugg KabelSensor HighwayOmnisensAFL GlobalQinetiQ GroupLockheed MartinOSENSA Innovati_预计2026年中国分布式传感器市场规模有多大
文章浏览阅读1.1k次,点赞2次,收藏12次。常用组合逻辑电路结构——为IC设计的延时估计铺垫学习目的:估计模块间的delay,确保写的代码的timing 综合能给到多少HZ,以满足需求!_基4布斯算法代码
文章浏览阅读3.3k次,点赞3次,收藏5次。OpenAI Manager助手(基于SpringBoot和Vue)_chatgpt网页版
文章浏览阅读2.2k次。USACO自1992年举办,到目前为止已经举办了27届,目的是为了帮助美国信息学国家队选拔IOI的队员,目前逐渐发展为全球热门的线上赛事,成为美国大学申请条件下,含金量相当高的官方竞赛。USACO的比赛成绩可以助力计算机专业留学,越来越多的学生进入了康奈尔,麻省理工,普林斯顿,哈佛和耶鲁等大学,这些同学的共同点是他们都参加了美国计算机科学竞赛(USACO),并且取得过非常好的成绩。适合参赛人群USACO适合国内在读学生有意向申请美国大学的或者想锻炼自己编程能力的同学,高三学生也可以参加12月的第_usaco可以多次提交吗
文章浏览阅读394次。1.1 存储程序1.2 创建存储过程1.3 创建自定义函数1.3.1 示例1.4 自定义函数和存储过程的区别1.5 变量的使用1.6 定义条件和处理程序1.6.1 定义条件1.6.1.1 示例1.6.2 定义处理程序1.6.2.1 示例1.7 光标的使用1.7.1 声明光标1.7.2 打开光标1.7.3 使用光标1.7.4 关闭光标1.8 流程控制的使用1.8.1 IF语句1.8.2 CASE语句1.8.3 LOOP语句1.8.4 LEAVE语句1.8.5 ITERATE语句1.8.6 REPEAT语句。_mysql自定义函数和存储过程
文章浏览阅读188次。半导体二极管——集成电路最小组成单元。_本征半导体电流为0
文章浏览阅读2.8k次,点赞3次,收藏18次。游戏水面特效实现方式太多。咱们这边介绍的是一最简单的UV动画(无顶点位移),整个mesh由4个顶点构成。实现了水面效果(左图),不动代码稍微修改下参数和贴图可以实现岩浆效果(右图)。有要思路是1,uv按时间去做正弦波移动2,在1的基础上加个凹凸图混合uv3,在1、2的基础上加个水流方向4,加上对雾效的支持,如没必要请自行删除雾效代码(把包含fog的几行代码删除)S..._unity 岩浆shader
文章浏览阅读5k次。广义线性模型是线性模型的扩展,它通过连接函数建立响应变量的数学期望值与线性组合的预测变量之间的关系。广义线性模型拟合的形式为:其中g(μY)是条件均值的函数(称为连接函数)。另外,你可放松Y为正态分布的假设,改为Y 服从指数分布族中的一种分布即可。设定好连接函数和概率分布后,便可以通过最大似然估计的多次迭代推导出各参数值。在大部分情况下,线性模型就可以通过一系列连续型或类别型预测变量来预测正态分布的响应变量的工作。但是,有时候我们要进行非正态因变量的分析,例如:(1)类别型.._广义线性回归模型
文章浏览阅读69次。环境保护、 保护地球、 校园环保、垃圾分类、绿色家园、等网站的设计与制作。 总结了一些学生网页制作的经验:一般的网页需要融入以下知识点:div+css布局、浮动、定位、高级css、表格、表单及验证、js轮播图、音频 视频 Flash的应用、ul li、下拉导航栏、鼠标划过效果等知识点,网页的风格主题也很全面:如爱好、风景、校园、美食、动漫、游戏、咖啡、音乐、家乡、电影、名人、商城以及个人主页等主题,学生、新手可参考下方页面的布局和设计和HTML源码(有用点赞△) 一套A+的网_垃圾分类网页设计目标怎么写
文章浏览阅读614次,点赞7次,收藏11次。之前找到一个修改 exe 中 DLL地址 的方法, 不太好使,虽然能正确启动, 但无法改变 exe 的工作目录,这就影响了.Net 中很多获取 exe 执行目录来拼接的地址 ( 相对路径 ),比如 wwwroot 和 代码中相对目录还有一些复制到目录的普通文件 等等,它们的地址都会指向原来 exe 的目录, 而不是自定义的 “lib” 目录,根本原因就是没有修改 exe 的工作目录这次来搞一个启动程序,把 .net 的所有东西都放在一个文件夹,在文件夹同级的目录制作一个 exe._.net dll 全局目录
文章浏览阅读1.5k次。本文为转载,原博客地址:http://blog.csdn.net/hujingshuang/article/details/46910259简介 BRIEF是2010年的一篇名为《BRIEF:Binary Robust Independent Elementary Features》的文章中提出,BRIEF是对已检测到的特征点进行描述,它是一种二进制编码的描述子,摈弃了利用区域灰度..._breif description calculation 特征点
文章浏览阅读4.1k次,点赞21次,收藏79次。本文是《基于SpringBoot的房屋租赁管理系统》的配套原创说明文档,可以给应届毕业生提供格式撰写参考,也可以给开发类似系统的朋友们提供功能业务设计思路。_基于spring boot的房屋租赁系统论文