[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

相关文章

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注