【C++ STL算法】二分查找 lower_bound、upper_bound、equal_range、binary_search

文章目录

  • 【 1. 首个不小于 lower_bound 】
  • 【 2. 首个大于 upper_bound 】
  • 【 3. 所有等于 equel_range 】
  • 【 4. 二分查找 binary_search 】

  • 当 指定区域内的数据处于有序状态 时，如果想查找某个目标元素，更推荐使用二分查找的方法（相比顺序查找，二分查找的执行效率更高）。
  • C++ STL标准库中提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是 二分查找 的方式。
  • 头文件 <algorithm>

【 1. 首个不小于 lower_bound 】

  • lower_bound() 函数用于在指定区域内 查找 首个不小于目标值 的元素。
  • 基本语法
    • first 和 last 都为正向迭代器，[first, last) 是指定查找范围，该 指定区域内必须已排序 。
    • val 为指定目标值。
    • comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
    • 该函数会 返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，若查找失败，迭代器的指向和 last 迭代器相同。
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val);

//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
  • 实例
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }//以函数对象的形式定义查找规则
class mycomp2 {
public:bool operator()(const int& i, const int& j) {return i < j;}
};int main() {//从 a 数组中找到第一个不小于 3 的元素int a[5] = { 1,2,3,4,5 };int* p = lower_bound(a, a + 5, 3);cout << "*p = " << *p << endl;//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素vector<int> myvector{ 1,2,3,4,5 };vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(), 3, mycomp2());cout << "*iter = " << *iter;return 0;
}

在这里插入图片描述

  • lower_bound() 函数底层实现的参考代码
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it;iterator_traits<ForwardIterator>::difference_type count, step;count = distance(first,last);while (count>0){it = first; step=count/2; advance (it,step);if (*it<val) {  //或者 if (comp(*it,val))，对应第 2 种语法格式first=++it;count-=step+1;}else count=step;}return first;
}

【 2. 首个大于 upper_bound 】

  • upper_bound() 函数 用于在指定范围内 查找 首个大于目标值 的元素。
  • 基本语法
    • first 和 last 都为正向迭代器，[first, last) 是查找范围，该 指定区域内必须已排序 。
    • val 为指定目标值。
    • comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
    • 该函数会 返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，若查找失败，迭代器的指向和 last 迭代器相同。
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);

//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
  • 实例
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }//以函数对象的形式定义查找规则
class mycomp2 {
public:bool operator()(const int& i, const int& j) {return i <  j;}
};int main() {//从 a 数组中找到第一个大于 3 的元素int a[5] = { 1,2,3,4,5 };int* p = upper_bound(a, a + 5, 3);cout << "*p = " << *p << endl;//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素vector<int> myvector{ 1,2,3,4,5 };vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());cout << "*iter = " << *iter;return 0;
}

在这里插入图片描述

  • upper_bound() 函数底层实现的参考代码
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it;iterator_traits<ForwardIterator>::difference_type count, step;count = std::distance(first,last);while (count>0){it = first; step=count/2; std::advance (it,step);if (!(val<*it))  // 或者 if (!comp(val,*it)), 对应第二种语法格式{ first=++it; count-=step+1;  }else count=step;}return first;
}

【 3. 所有等于 equel_range 】

  • equel_range() 函数用于在指定范围内查找 所有等于目标值的元素 。
  • 基本语法
    • first 和 last 都为正向迭代器，[first, last) 是查找范围，该 指定区域内必须已排序 。
    • val 为指定目标值。
    • comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
    • 该函数会 返回一个 pair 类型值 ，其包含 2 个正向迭代器。
      • 查找成功时：第 1 个迭代器指向的是 [first, last) 区域中 第一个等于 val 的元素；第 2 个迭代器指向的是 [first, last) 区域中 第一个大于 val 的元素 。
      • 查找失败时：这 2 个迭代器要么 都指向大于 val 的第一个元素（如果有），要么 都和 last 迭代器指向相同 。
类型基本语法1基本语法2
条件指定范围内的数据支持用 < 小于运算符直接做比较指定范围内的数据为自定义的类型（用结构体或类），就需要自定义比较规则
语法//找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);		//找到 [first, last) 范围内所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
  • 实例
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }//以函数对象的形式定义查找规则
class mycomp2 {
public:bool operator()(const int& i, const int& j) {return i > j;}
};int main() {//从 a 数组中找到所有的元素 4int a[9] = { 1,2,3,4,4,4,5,6,7 };pair<int*, int*> range = equal_range(a, a + 9, 4);cout << "a[9]：";for (int* p = range.first; p < range.second; ++p) {cout << *p << " ";}//在 myvector 容器中找到所有的元素 3vector<int>myvector{ 7,8,5,4,3,3,3,3,2,1 };pair<vector<int>::iterator, vector<int>::iterator> range2;range2 = equal_range(myvector.begin(), myvector.end(), 3, mycomp2());cout << "\nmyvector：";for (auto it = range2.first; it != range2.second; ++it) {cout << *it << " ";}return 0;
}

在这里插入图片描述

  • equel_range() 函数底层实现的参考代码
//对应第一种语法格式
template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it = std::lower_bound (first,last,val);return std::make_pair ( it, std::upper_bound(it,last,val) );
}
//对应第二种语法格式
template<class ForwardIterator, class T, class Compare>
std::pair<ForwardIt,ForwardIt> equal_range(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)
{ForwardIterator it = std::lower_bound (first,last,val,comp);return std::make_pair ( it, std::upper_bound(it,last,val,comp) );
}

【 4. 二分查找 binary_search 】

  • binary_search() 函数用于查找指定区域内 是否包含某个目标元素 。
  • 基本语法
    • first 和 last 都为正向迭代器，[first, last) 是查找范围，该 指定区域内必须已排序 。
    • val 为指定目标值。
    • comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
    • 该函数会 返回一个 bool 类型值 ：
      • 如果 binary_search() 函数在 [first, last) 区域内 成功找到和 val 相等的元素，则返回 true ；
      • 反之则返回 false。
类型基本语法1基本语法2
条件查找 [first, last) 区域内是否包含 val根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
语法bool binary_search (ForwardIterator first, ForwardIterator last,const T& val); bool binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
  • 实例
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }//以函数对象的形式定义查找规则
class mycomp2 {
public:bool operator()(const int& i, const int& j) {return i > j;}
};
int main() {//从 a 数组中查找元素 4int a[7] = { 1,2,3,4,5,6,7 };bool haselem = binary_search(a, a + 9, 4);cout << "haselem：" << haselem << endl;//从 myvector 容器查找元素 3vector<int>myvector{ 4,5,3,2,1 };bool haselem2 = binary_search(myvector.begin(), myvector.end(), 3, mycomp2());cout << "haselem2：" << haselem2;return 0;
}

在这里插入图片描述

  • binary_search() 函数底层实现的参考代码
//第一种语法格式的实现
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{first = std::lower_bound(first,last,val);return (first!=last && !(val<*first));
}
//第二种语法格式的底层实现
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& val, Compare comp)
{first = std::lower_bound(first, last, val, comp);return (!(first == last) && !(comp(val, *first)));
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/444129.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

电影选票选座系统|影院购票|电影院订票选座小程序|基于微信小程序的电影院购票系统设计与实现(源码+数据库+文档)

电影选票选座系统|影院购票|电影院订票选座小程序|基于微信小程序的电影院购票系统设计与实现(源码+数据库+文档)

电影院订票选座小程序 目录 基于微信小程序的电影院购票系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户功能实现 2、管理员功能实现 &#xff08;1&#xff09;影院信息管理 &#xff08;2&#xff09;电影信息管理 &#xff08;3&#xff09;已完成…
阅读更多...
Internet Download Manager6.42免费版下载神器新体验

Internet Download Manager6.42免费版下载神器新体验

&#x1f680; 开篇就燃&#xff01;你的下载速度被“TA”承包了 #### &#x1f31f; 初识IDM 6.42&#xff0c;下载界的“超跑”驾到 各位追求效率的小伙伴们&#xff0c;今天小红要来揭秘一款让我彻底告别“龟速”下载的神器——Internet Download Manager (简称IDM) 6.42版&…
阅读更多...
xtu oj 四位数

xtu oj 四位数

样例输入# 2 1990 1111样例输出# 5 0 分离整数与合并 AC代码 #include<stdio.h> //判断四个数码是否相等 int Judge(int n){int flag1;int gn%10,sn/10%10,bn/100%10,qn/1000;if(gs&&gb&&gq)flag0;return flag; } int main(){int T;scanf("%d…
阅读更多...
dayu_widgets-简介

dayu_widgets-简介

前言: 越来越多的人开始使用python来做GUI程序&#xff0c;市面上却很少有好的UI控件。即使有也是走的商业收费协议&#xff0c;不敢使用&#xff0c;一个不小心就收到法律传票。 一、原始开源项目: 偶然在GitHub上发现了这个博主的开源项目。https://github.com/phenom-films…
阅读更多...
抽象类Abstart Class

抽象类Abstart Class

抽象类其实就是一种不完全的设计图 必须用abstract修饰 模板方法&#xff1a;建议使用final修饰&#xff0c;不能被重写。
阅读更多...
DGL库之HGTConv的使用

DGL库之HGTConv的使用

DGL库之HGTConv的使用 论文地址和异构图构建教程HGTConv语法格式HGTConv的使用 论文地址和异构图构建教程 论文地址&#xff1a;https://arxiv.org/pdf/2003.01332 异构图构建教程&#xff1a;异构图构建 异构图转同构图&#xff1a;异构图转同构图 HGTConv语法格式 dgl.nn.…
阅读更多...
AI智能聊天问答系统源码+AI绘画系统+图文搭建部署教程，文生图图生图，TTS语音识别输入，AI智能体，文档分析

AI智能聊天问答系统源码+AI绘画系统+图文搭建部署教程，文生图图生图，TTS语音识别输入，AI智能体，文档分析

一、前言 人工智能的快速进步吸引了全球的瞩目&#xff0c;各式AI应用如绘图、语言模型和视频处理等已在多个领域获得应用。这些技术不仅加速了科技的创新&#xff0c;也在艺术创作、内容生产和商业实践等方面显示了其巨大潜力。例如&#xff0c;AI语言模型极大提升了内容自动…
阅读更多...
【动态规划-最长公共子序列（LCS）】【hard】【科大讯飞笔试最后一题】力扣115. 不同的子序列

【动态规划-最长公共子序列（LCS）】【hard】【科大讯飞笔试最后一题】力扣115. 不同的子序列

给你两个字符串 s 和 t &#xff0c;统计并返回在 s 的 子序列 中 t 出现的个数&#xff0c;结果需要对 10^9 7 取模。 示例 1&#xff1a; 输入&#xff1a;s “rabbbit”, t “rabbit” 输出&#xff1a;3 解释&#xff1a; 如下所示, 有 3 种可以从 s 中得到 “rabbit”…
阅读更多...
ABAP 表转JSON格式

ABAP 表转JSON格式

FUNCTION ZRFC_FI_SEND_PAYPLAN2BPM. *"---------------------------------------------------------------------- *"*"本地接口&#xff1a; *" IMPORTING *" VALUE(INPUT) TYPE ZSRFC_FI_SEND_PAYBPM_IN *" EXPORTING *" VAL…
阅读更多...
vue3数字滚动插件vue3-count-to

vue3数字滚动插件vue3-count-to

1.安装 npm i vue3-count-to 2.引入 import { CountTo } from vue3-count-to3.使用 <countTo :startVal"0" :endVal"57.63" :decimals"2" :duration"3000"></countTo> 配置项:
阅读更多...
yolov5-7.0模型DNN加载函数及参数详解(重要)

yolov5-7.0模型DNN加载函数及参数详解(重要)

yolov5-7.0模型DNN加载函数及参数详解&#xff08;重要&#xff09; 引言yolov5&#xff08;v7.0&#xff09;1&#xff0c;yolov5.h(加载对应模型里面的相关参数要更改)2&#xff0c;main主程序&#xff08;1&#xff09;加载网络&#xff08;2&#xff09;检测推理&#xff0…
阅读更多...
AVL树如何维持平衡

AVL树如何维持平衡

1.AVL树的特性 二叉搜索树虽可以缩短查找的效率&#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树&#xff0c;查 找元素相当于在顺序表中搜索元素&#xff0c;效率低下。因此&#xff0c;两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种…
阅读更多...
【万字长文】Word2Vec计算详解（一）CBOW模型

【万字长文】Word2Vec计算详解（一）CBOW模型

【万字长文】Word2Vec计算详解&#xff08;一&#xff09;CBOW模型 写在前面 本文用于记录本人学习NLP过程中&#xff0c;学习Word2Vec部分时的详细过程&#xff0c;本文与本人写的其他文章一样&#xff0c;旨在给出Word2Vec模型中的详细计算过程&#xff0c;包括每个模块的计…
阅读更多...
【redis-06】redis的stream流实现消息中间件

【redis-06】redis的stream流实现消息中间件

redis系列整体栏目 内容链接地址【一】redis基本数据类型和使用场景https://zhenghuisheng.blog.csdn.net/article/details/142406325【二】redis的持久化机制和原理https://zhenghuisheng.blog.csdn.net/article/details/142441756【三】redis缓存穿透、缓存击穿、缓存雪崩htt…
阅读更多...
Auto-Animate：是一款零配置、即插即用的动画工具，可以为您的 Web 应用添加流畅的过渡效果

Auto-Animate：是一款零配置、即插即用的动画工具，可以为您的 Web 应用添加流畅的过渡效果

嗨&#xff0c;大家好&#xff0c;我是小华同学&#xff0c;关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 用户体验成为了检验产品成功与否的关键因素。而动画效果&#xff0c;作为提升用户体验的重要手段&#xff0c;在网页和应用开发中扮演着举足轻重的角色…
阅读更多...
同望OA tooneAssistantAttachement.jsp 任意文件读取漏洞复现

同望OA tooneAssistantAttachement.jsp 任意文件读取漏洞复现

0x01 产品简介 同望OA，即同望科技打造的智企云协同管理系统，是一款高效的企业协同移动办公系统。秉承“互联网++企业管理”理念，定位于以移动互联办公为基础的企业协同管理软件平台。它旨在通过内置常用标准模块与专项管理模块应用，安全快速地打通管理与业务通道，实现管理…
阅读更多...
QT 实现QMessageBox::about()信息自定义显示

QT 实现QMessageBox::about()信息自定义显示

这是我记录Qt学习过程的第四篇心得文章&#xff0c;主要是方便自己编写的应用程序显示“关于信息”&#xff0c;对QMessageBox::about()输入信息进行规范&#xff0c;可以设置应用程序名称&#xff0c;通过定义宏从pro文件获取应用程序版本号&#xff0c;以及编译程序的QT版本、…
阅读更多...
写一个代码：打印100~200之间的素数

写一个代码：打印100~200之间的素数

我们要输出100-200之间的素数&#xff0c;首先我们先得输出100-200之间的数字&#xff0c;一般用于遍历循环的数字要用到for循环&#xff0c;同时在输出的100~200之间的数字进行判断是不是素数&#xff0c;我们知道素数的判断条件在于当一个数字从1开始到自己本身的时候&#x…
阅读更多...
2024年最新（AI绘画）Stable Diffusion4.9下载及安装教程.

2024年最新（AI绘画）Stable Diffusion4.9下载及安装教程.

软件介绍 Stable Diffusion 是一款在图像生成领域具有重大影响力的软件。 从工作原理上看&#xff0c;它利用深度学习的先进算法&#xff0c;构建起复杂且强大的神经网络架构。其核心在于能够解读用户输入的文本信息&#xff0c;并将这些信息转化为图像的特征与细节。 在使用…
阅读更多...
【C++网络编程】（一）Linux平台下TCP客户/服务端程序

【C++网络编程】（一）Linux平台下TCP客户/服务端程序

文章目录 Linux平台下TCP客户/服务端程序服务端客户端相关头文件介绍 Linux平台下TCP客户/服务端程序 图片来源&#xff1a;https://subingwen.cn/linux/socket/ 下面实现一个Linux平台下TCP客户/服务端程序&#xff1a;客户端向服务器发送&#xff1a;“你好&#xff0c;服务…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023