[STL] 标准二分算法模板 lower_bound() upper_bound()代码解析

2024-02-07 03:38

本文主要是介绍[STL] 标准二分算法模板 lower_bound() upper_bound()代码解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、摘要

二分算法是经常使用的算法之一,熟练使用二分算法是一个程序员的基本素养。C++的<algorithm>头文件中存在lower_bound()upper_bound()函数,支持在已排好序的容器中查找首个大于等于或者大于目标元素的迭代器位置。同时在有序容器类,例如set<>和map<>,也存在类似功能的函数。熟练使用lower_bound()upper_bound()函数可以方便地使用二分算法解决问题。本文基于< algorithm>源代码,对lower_bound()upper_bound()代码进行分析解释,对于实现严谨高效的二分算法具有重要参考价值。

本文在第二部分给出<algorithm>头文件中lower_bound()upper_bound()函数的代码,并对代码进行分析解释;第三部分是对二分算法的实现,并注明了实现中需要注意的事项;最后一部分是本文参考文章链接。

二、官方代码

1. lower_bound(first, last, value)

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)。

2. upper_bound(first, last, value)

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;} elsecount = step;}return first;
}

三、二分算法实现

1. 二分算法实现

基于第二部分中给出的代码,我们参考其代码结构给出二分算法的实现。
算法需要解决的问题为,给出一个递增数组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

2. 注意事项

  • 使用二分算法要求数组有序(递增)。若数组递减,可以使用lower_bound(first, last, cmp)函数自定义比较函数。
  • 在while()循环中每次都要使count变为上次循环的一半大小(或者一半减一),不然容易造成死循环。

四、参考

[1]. std::lower_bound
[2]. std::upper_bound

这篇关于[STL] 标准二分算法模板 lower_bound() upper_bound()代码解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/686422

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使