当前位置: 首页 > news >正文

C++ 中 lower_bound 与 upper_bound 函数详解

C++ 中 lower_boundupper_bound 函数详解

文章目录

      • C++ 中 `lower_bound` 与 `upper_bound` 函数详解
        • **一、核心定义与区别**
        • **二、使用条件与时间复杂度**
        • **三、实际应用场景**
        • **四、注意事项与常见误区**
        • **五、代码示例**
        • **六、总结**

一、核心定义与区别
  1. lower_bound

    • 作用:在有序序列中查找第一个不小于目标值的元素位置
    • 返回值:若目标值存在,返回第一个匹配元素的迭代器;若不存在,返回首个大于目标值的元素的迭代器
    • 示例:在序列{1,2,4,4,5} 中查找 4,返回第一个4 的位置(索引 2)
    • 用lower_bound在{12,15,17,19,20,22,23,26,29,35,40,51},查找21时返回22的索引位置
  2. upper_bound

    • 作用:在有序序列中查找第一个大于目标值的元素位置
    • 返回值:若目标值存在,返回最后一个匹配元素的下一个位置;若不存在,行为与lower_bound一致
    • 示例:在相同序列{1,2,4,4,5}中查找4,返回第一个 5的位置(索引 4)
    • 用up_bound在{12,15,17,19,20,22,23,26,29,35,40,51},查找21时返回22的位置
  3. 关键区别

    特性lower_boundupper_bound
    等价元素处理指向第一个等价元素指向最后一个等价元素的下一个位置
    插入位置插入后位于相同元素之前插入后位于相同元素之后
    目标值不存在时返回值第一个大于目标值的元素位置同上

二、使用条件与时间复杂度
  1. 前提条件
    • 序列必须已按升序排列(或按自定义比较规则有序)。若未排序,结果未定义。
  2. 时间复杂度
    • 均为 O(log n),基于二分查找实现

三、实际应用场景
  1. 检查元素是否存在
    结合 lower_bound 的返回值与目标值比较:

    bool exists = (lower_bound(v.begin(), v.end(), target) != v.end()) && (*it == target);
    
  2. 统计元素出现次数
    使用 upper_bound - lower_bound 计算区间跨度:

    int count = upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target);
    
  3. 自定义排序规则
    支持传入比较函数,处理复杂数据结构或非默认排序:

    // 按个位数排序的数组
    bool cmp(int a, int b) { return a % 10 < b % 10; }
    auto it = lower_bound(arr, arr + n, 36, cmp); // 查找个位数 >=6 的第一个元素
    
  4. 插入元素保持有序性
    在有序容器中插入新元素时,确定插入位置

    auto pos = upper_bound(v.begin(), v.end(), new_value);
    v.insert(pos, new_value); // 插入后序列仍有序
    

四、注意事项与常见误区
  1. 必须保证序列有序

    • 未排序时调用会导致未定义行为。例如,对乱序数组调用可能返回错误位置
  2. 迭代器越界检查

    • 需验证返回值是否为end(),避免解引用无效迭代器
  3. 自定义比较函数的一致性

    • 比较函数必须与序列排序规则一致。例如,降序序列需使用greater而非默认的 less
  4. 等价元素的处理差异

    • 若需获取所有等价元素的范围,建议使用equal_range(返回lower_bound和upper_bound

      的 pair 结果)


五、代码示例
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;int main() {vector<int> v = {1, 2, 4, 4, 5, 7, 8};int target = 4;// lower_bound 示例auto low = lower_bound(v.begin(), v.end(), target);cout << "lower_bound 位置: " << (low - v.begin()) << ",值: " << *low << endl; // 输出 2, 4// upper_bound 示例auto up = upper_bound(v.begin(), v.end(), target);cout << "upper_bound 位置: " << (up - v.begin()) << ",值: " << *up << endl; // 输出 4, 5return 0;
}

六、总结

lower_boundupper_bound 是处理有序序列的核心工具,适用于高效查找、统计和插入操作。使用时需严格保证序列的有序性,并根据场景选择是否需要自定义比较规则。通过灵活组合这两个函数,可以解决大多数与有序数据相关的算法问题。

相关文章:

C++ 中 lower_bound 与 upper_bound 函数详解

C 中 lower_bound 与 upper_bound 函数详解 文章目录 C 中 lower_bound 与 upper_bound 函数详解**一、核心定义与区别****二、使用条件与时间复杂度****三、实际应用场景****四、注意事项与常见误区****五、代码示例****六、总结** 一、核心定义与区别 lower_bound 作用&#…...

minio数据迁移(两台服务器没法相互通信)

场景描述: A服务器 无法访问 B服务器&#xff0c;B服务器 也无法访问 A&#xff08;即双方都不能通过公网或内网直连对方&#xff09; MinIO 官方提供了 mc&#xff08;MinIO Client&#xff09;命令行工具&#xff0c;可以直接实现 Bucket 之间的数据迁移&#xff1a; 安装 …...

O2OA(翱途)开发平台系统安全-用户登录IP限制

O2OA(翱途)开发平台[下称O2OA开发平台或者O2OA]支持对指定的用户设置可以连接的客户端计算机的IP地址&#xff0c;以避免用户在不安全的环境下访问系统。本篇主要介绍如何开启O2OA用户登录IP限制。 一、先决条件&#xff1a; 以拥有管理员权限的用户账号登录O2OA(翱途)开发平…...

CSS flex:1

在 CSS 中&#xff0c;flex: 1 是一个用于弹性布局&#xff08;Flexbox&#xff09;的简写属性&#xff0c;主要用于控制 flex 项目&#xff08;子元素&#xff09;如何分配父容器的剩余空间。以下是其核心作用和用法&#xff1a; 核心作用 等分剩余空间&#xff1a;让 flex …...

OpenHarmony平台驱动开发(十一),PIN

OpenHarmony平台驱动开发&#xff08;十一&#xff09; PIN 概述 功能简介 PIN即管脚控制器&#xff0c;用于统一管理各SoC的管脚资源&#xff0c;对外提供管脚复用功能。 基本概念 PIN是一个软件层面的概念&#xff0c;目的是为了统一对各SoC的PIN管脚进行管理&#xff0…...

.NET高频技术点(持续更新中)

1. .NET 框架概述 .NET 框架的发展历程.NET Core 与 .NET Framework 的区别.NET 5 及后续版本的统一平台 2. C# 语言特性 异步编程&#xff08;async/await&#xff09;LINQ&#xff08;Language Integrated Query&#xff09;泛型与集合委托与事件属性与索引器 3. ASP.NET…...

Spring Cloud - 2( 12000 字详解 Spring Cloud)

一&#xff1a;服务注册和服务发现 - Eureka 1.1 背景 在上一章节的例子中&#xff0c;我们可以看到远程调用时 URL 被硬编码&#xff0c;这导致在更换机器或新增机器时&#xff0c;相关的 URL 需要进行相应的变更。这就需要让所有相关服务去修改 URL&#xff0c;随之而来的就…...

解决Win11下MySQL服务无法开机自启动问题

问题描述 在win11系统中&#xff0c;明明将MySQL服务设置成了自动启动&#xff0c;但在重启电脑后MySQL服务还是无法自动启动&#xff0c;每次都要重新到计算机管理的服务中找到服务再手动启动。 解决方式 首先确保mysql服务的启动类型为自动。 设置方法&#xff1a;找到此电…...

RGB矩阵照明系统详解及WS2812配置指南

RGB矩阵照明系统详解及WS2812配置指南 一、RGB矩阵照明简介 RGB矩阵照明是一种强大的功能&#xff0c;允许使用外部驱动器驱动的RGB LED矩阵为键盘增添绚丽的灯光效果。该系统与RGBLIGHT功能无缝集成&#xff0c;因此您可以使用与RGBLIGHT相同的键码来控制它&#xff0c;操作…...

全球首款无限时长电影生成模型SkyReels-V2本地部署教程:视频时长无限制!

一、简介 SkyReels-V2 模型集成了多模态大语言模型&#xff08;MLLM&#xff09;、多阶段预训练、强化学习以及创新的扩散强迫&#xff08;Diffusion-forcing&#xff09;框架&#xff0c;实现了在提示词遵循、视觉质量、运动动态以及视频时长等方面的全面突破。通过扩散强迫框…...

代理ARP与传统ARP在网络通信中的应用及区别研究

一些问题 路由器隔离广播域&#xff0c;每个接口/网段都是独立的广播域ARP请求是二层广播包&#xff0c;广播包没法通过路由器ARP请求没法穿越互联网到达目标主服务器 一些思考 电脑访问互联网服务器的时候&#xff0c;ARP询问的内容&#xff0c;真的是访问服务器么&#xf…...

理解 Envoy 的架构

理解 Envoy 的架构对于深入理解 Istio 至关重要&#xff0c;因为 Envoy 是 Istio 数据平面的核心。Envoy 是一个高性能的 C 分布式代理&#xff0c;设计为云原生应用和大规模微服务架构的网络基础。 以下是 Envoy 架构的关键组成部分和核心理念&#xff1a; 核心设计理念&…...

使用Kotlin Flow实现Android应用的响应式编程

在Android应用中使用Kotlin Flow实现响应式编程可以分为以下步骤&#xff0c;结合最佳实践和生命周期管理&#xff1a; 1. 添加依赖 在build.gradle中确保包含协程和生命周期相关依赖&#xff1a; dependencies {implementation("org.jetbrains.kotlinx:kotlinx-corouti…...

【AI提示词】蝴蝶效应专家

提示说明 一位专注于分析和优化蝴蝶效应现象的专业人士&#xff0c;擅长将微小变化转化为系统级影响的研究者。 提示词 # Role: 蝴蝶效应专家## Profile - language: 中文 - description: 一位专注于分析和优化蝴蝶效应现象的专业人士&#xff0c;擅长将微小变化转化为系统级…...

StreamRL:弹性、可扩展、异构的RLHF架构

StreamRL&#xff1a;弹性、可扩展、异构的RLHF架构 大语言模型&#xff08;LLMs&#xff09;的强化学习&#xff08;RL&#xff09;训练正处于快速发展阶段&#xff0c;但现有架构存在诸多问题。本文介绍的StreamRL框架为解决这些难题而来&#xff0c;它通过独特设计提升了训…...

架构进阶:大型制造业企业数据架构顶层设计总体规划方案【附全文阅读】

本文概述了一个大型企业数据架构设计的总体规划方案,针对当前数据架构与管理中存在的诸多问题,如缺乏统一数据模型、数据分析应用体系不健全、主数据管理体系不完善、数据治理体系缺失等,提出了明确的改进目标与实施路径。 数据架构设计思路聚焦于明确数据分布和流向…...

前端指南——项目代码结构解析(React为例)

文件结构 文件项目 ├── doc │ ├── technology.md ├── node_modules ├── public ├── shell ├── src │ ├── auto-generated │ │ ├── apis │ │ ├── models │ ├── components │ │ ├── 组件A │ │ ├── 组件B …...

Redis-数据一致性问题与解决方案

Redis-数据一致性问题与解决方案 引言 Redis 是一个高性能的内存数据库&#xff0c;广泛应用于缓存、会话存储、实时分析等场景。作为一个 NoSQL 数据库&#xff0c;它的高性能和丰富的数据结构使其成为现代微服务架构中不可或缺的组件。然而&#xff0c;在高并发的环境下&am…...

【数据结构】算法的复杂度

前言&#xff1a;经过了C语言的学习&#xff0c;紧接着就步入到数据结构的学习了。在C语言阶段我们在写大多数的oj题的时候会遇到一些问题&#xff0c;就是算法的效率低使用的时间较多&#xff0c;占用的空间也多&#xff0c;数据结构就是来优化算法的。 文章目录 一&#xff…...

Leetcode刷题 由浅入深之字符串——541. 反转字符串Ⅱ

目录 &#xff08;一&#xff09;反转字符串Ⅱ的C实现 写法一&#xff08;s.begin&#xff08;&#xff09;遍历字符&#xff09; &#xff08;二&#xff09;复杂度分析 时间复杂度 空间复杂度 &#xff08;三&#xff09;总结 【题目链接】541. 反转字符串Ⅱ - 力扣&am…...

制造单元智能化改造与集成技术平台成套实训设备

制造单元智能化改造与集成技术平台成套实训设备 一、概述&#xff1a; 本设备以汽车行业的轮毂为产品对象&#xff0c;实现了仓库取料、制造加工、打磨抛光、检测识别、分拣入位等生产工艺环节&#xff0c;以未来智能制造工厂的定位和需求为参考&#xff0c;通过工业以太网完成…...

Vscode 顶部Menu(菜单)栏消失如何恢复

Vscode 顶部Menu(菜单)栏消失如何恢复 https://blog.csdn.net/m0_62964247/article/details/135759655 Vscode 顶部Menu(菜单)栏消失如何恢复&#xff1f; 首先按一下 Alt按键&#xff0c;看一下是否恢复了菜单栏 如果恢复了想了解更进一步的设置&#xff0c;或是没能恢复菜单…...

苍穹外卖--公共字段自动填充

1.问题分析 业务表中的公共字段&#xff1a; 问题&#xff1a;代码冗余、不便于后期维护 2.实现思路 自定义注解AutoFill&#xff0c;用于标识需要进行公共字段填充的方法 自定义切面类AutoFillAspect&#xff0c;统一拦截加入了AutoFill注解的方法&#xff0c;通过反射为公…...

行业 |四大痛点待破:“拆解”DeepSeek一体机

繁荣DeepSeek一体机市场。 2025年开年&#xff0c;DeepSeek大模型掀起的一体机热潮席卷中国AI市场。这款一体机凭借其“开箱即用”的便利性和极低的门槛&#xff0c;吸引了大量企业关注&#xff0c;尤其是在中小企业和行业创新者中&#xff0c;更是成为了新晋“顶流”。 无论…...

革新锅炉厂智能控制——Ethernet IP转CANopen协议网关的工业互联新方案

锅炉厂智能化转型的必经之路 在工业4.0时代&#xff0c;锅炉厂作为能源供应的核心环节&#xff0c;正面临智能化升级的迫切需求。传统锅炉控制系统往往因协议不兼容、数据孤岛问题导致效率低下、维护成本高昂。如何实现设备间高效协同&#xff1f;如何让老旧设备融入智能网络&…...

基于卷积神经网络和Pyqt5的猫狗识别小程序

任务描述 猫狗分类任务&#xff08;Dogs vs Cats&#xff09;是Kaggle平台在2013年举办的一个经典计算机视觉竞赛。官方给出的Kaggle Dogs vs Cats 数据集中包括由12500张猫咪图片和12500张狗狗图片组成的训练集&#xff0c;12500张未标记照片组成的测试集。选手需要在规定时间…...

Baklib知识中台引领服务智能跃迁

智能架构重构服务范式 Baklib 知识中台通过全量数据融合与多模态处理能力&#xff0c;重塑企业服务底层逻辑。基于分布式架构设计&#xff0c;平台将分散在业务系统、文档库及外部渠道的非结构化数据进行智能清洗与语义解析&#xff0c;形成标准化的知识元数据池。通过四库体系…...

【Python】超全常用 conda 命令整理

Conda命令整理文档&#xff0c;结合官方指南与高频使用场景分类说明&#xff0c;每个命令都有对应的解释 一、环境管理 1. 创建环境 基本创建conda create --name my_env # 创建名为my_env的空环境 conda create -n my_env python3.11 # 指定Python版本 conda creat…...

FreeRTOS菜鸟入门(十四)·事件

目录 1. 基本概念 2. 应用场景 3. 运作机制 4. 控制块 5. 事件函数接口 5.1 事件创建函数 xEventGroupCreate() 5.2 事件删除函数 vEventGroupDelete() 5.3 事件组置位函数 xEventGroupSetBits()&#xff08;非中断&#xff09; 5.4 事件组置位函数 xEventGr…...

setData执行后操作方法-微信小程序

在微信小程序中&#xff0c;setData 是异步执行的&#xff0c;如果你需要在 setData 执行完毕后执行某些操作&#xff0c;可以通过以下几种方式实现&#xff1a; 1. 使用 setData 的回调函数 从基础库 2.2.3 开始&#xff0c;setData 支持传入回调函数&#xff0c;回调会在数据…...

SpringAI特性

一、SpringAI 顾问&#xff08;Advisors&#xff09; Spring AI 使用 Advisors机制来增强 AI 的能力&#xff0c;可以理解为一系列可插拔的拦截器&#xff0c;在调用 AI 前和调用 AI 后可以执行一些额外的操作&#xff0c;比如&#xff1a; 前置增强&#xff1a;调用 AI 前改…...

捌拾叁- 量子傅里叶变换

1. 前言 最近公司地震&#xff0c;现在稍微有点时间继续学习。 看了几个算法&#xff0c;都说是基于 量子傅里叶变换 &#xff0c;好&#xff0c;就是他了 Quantum Fourier。 2. 傅里叶变换 大学是学通信的&#xff0c;对于傅里叶变换还是有所理解的。其实就是基于一个 时域…...

SSTI模版注入

1、概念 SSTI是一种常见的Web安全漏洞&#xff0c;它允许攻击者通过注入恶意模板代码&#xff0c;使服务器在渲染模板时执行非预期的操作。 &#xff08;1&#xff09;渲染模版 至于什么是渲染模版&#xff1a;服务器端渲染模板是一种Web开发技术&#xff0c;它允许在服务器端…...

33、前台搜索功能怎么实现?

输入搜索的东西&#xff0c;如果为空 如果有 前端是提交表单&#xff0c;方式是 post 后端接受 调用 mybatisplus的categoryService.getById 用户在搜索框内输入关键字之后&#xff0c;执行 js 中的 load方法&#xff0c;前端提交表单&#xff0c; 后端 controller 中的loa…...

量化解析美英协议的非对称冲击:多因子模型与波动率曲面重构

摘要&#xff1a;基于机器学习算法对市场微观结构的实时监测&#xff0c;黄金价格在3300美元/盎司附近展开技术性反弹。本文通过多因子分析框架&#xff0c;解析美元指数上行、贸易政策突变及资产配置迁移对贵金属市场的复合影响&#xff0c;并构建基于LSTM神经网络的动态支撑位…...

对PyTorch模块进行性能分析

以下是针对PyTorch模块进行性能分析的完整方法与工具指南&#xff0c;结合了多种优化策略和实际应用场景&#xff1a; 一、PyTorch性能分析工具 PyTorch Profiler • 功能&#xff1a;内置的性能分析工具&#xff0c;支持捕获CPU/GPU操作、内存分配、数据形状及硬件利用率。 …...

lvm详细笔记

LVM简介 逻辑卷管理器&#xff0c;是Linux 系统中用于管理磁盘储存的关键技术。 LVM 则打破了磁盘分区一旦确定&#xff0c;其大小调整往往较为复杂&#xff0c;且难以灵活应对业务变化这种限制&#xff0c;它允许用户将多个物理分区组合卷组。例如&#xff0c;系统中的多个物…...

OpenHarmony 以太网卡热插拔事件接口无效

目录 1.背景 2.解决方案 1.背景 在OpenHarmony中调用以太网热插拔时间&#xff0c;发现热插拔没有任何回调&#xff0c;如下接口 import { ethernet } from kit.NetworkKit;ethernet.on(interfaceStateChange, (data: object) > {console.log(on interfaceSharingStateCha…...

SPDK NVMe of RDMA 部署

使用SPDK NVMe of RDMA 实现多NVMe设备共享 一、编译、安装spdk 1.1、下载 1.1.1 下载spdk源码 首先&#xff0c;我们需要从GitHub上克隆SPDK的源码仓库。打开终端&#xff0c;输入以下命令&#xff1a; git clone -b v22.01 https://github.com/spdk/spdk.git cd spdk1.1.2…...

Go语言的逃逸分析是怎么进行的

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…...

纯净IP,跨境账号稳定的底层逻辑

在跨境业务快速扩张的背景下&#xff0c;越来越多的卖家、营销人、数据团队都开始使用代理IP来实现全球网络触达。然而&#xff0c;账号封禁问题始终如影随形&#xff0c;而背后的一个“隐性元凶”常常被忽视——纯净IP的缺失。本文将从实战角度出发&#xff0c;带你深入了解什…...

编译日志:关于编译opencv带有ffmpeg视频解码支持的若干办法

编译日志&#xff1a;关于编译opencv带有ffmpeg视频解码支持的若干办法 前言 ​ 笔者这里是封装了简单的OpenCV视频播放抽象&#xff0c;然后却发现移植到Ubuntu和开发板上都罢工的事情&#xff0c;原来是Windows平台下我们是默认下载了ffmpeg的库的&#xff0c;但是在泛Linu…...

djinn: 3靶场渗透

djinn: 3 来自 <https://www.vulnhub.com/entry/djinn-3,492/> 1&#xff0c;将两台虚拟机网络连接都改为NAT模式 2&#xff0c;攻击机上做namp局域网扫描发现靶机 nmap -sn 192.168.23.0/24 那么攻击机IP为192.168.23.182&#xff0c;靶场IP192.168.23.243 3&#xff0…...

WHAT - 简单服务发现

文章目录 简单理解举个例子简单服务发现方式1. 静态配置&#xff08;最简单&#xff0c;但不灵活&#xff09;2. DNS 发现3. 使用服务注册中心&#xff08;稍高级&#xff09; 总结 “简单服务发现”&#xff08;Simple Service Discovery&#xff09;通常指的是一种让系统中的…...

auto推导类型原则

auto 是 C11 引入的类型自动推导关键字&#xff0c;它允许编译器根据表达式的类型来推导变量的确切类型。虽然使用 auto 可以让代码更简洁&#xff0c;但理解它的类型推导规则非常关键&#xff0c;尤其是在涉及指针、引用、const、模板等场景时。 ✅ 一、基本推导原则 auto x …...

44.辐射发射整改简易摸底测试方法

辐射发射整改简易摸底测试方法 1. 正式摸底预测试2. 简易方法预测试3. 分析频谱4. 探查传播路径5. 施加措施6. 与简易方法预测试效果对比 1. 正式摸底预测试 去正式实验室做一次预测试&#xff0c;取得频谱图&#xff1b;确定超标频点和超标量&#xff08;备用&#xff09;。 …...

初识C++:入门基础(二)

概述&#xff1a;该篇博客主要介绍C的缺省函数、函数重载、和引用等知识。 目录 1. 缺省参数 2. 函数重载 3. 引用 3.1 引用的概念和定义 3.2 引用的特性 3.3 引用的使用 3.4 const引用 3.5 指针和引用的关系 4. nullptr 5. 小结 1. 缺省参数 缺省参数是声明或定义函…...

我国脑机接口市场规模将破38亿元,医疗领域成关键突破口

当人类仅凭"意念"就能操控无人机编队飞行&#xff0c;当瘫痪患者通过"脑控"重新站立行走&#xff0c;这些曾只存在于科幻电影的场景&#xff0c;如今正通过脑机接口技术变为现实。作为"十四五"规划中重点发展的前沿科技&#xff0c;我国脑机接口…...

笔记,麦克风的灵敏度

麦克风的“灵敏度&#xff08;Sensitivity&#xff09;”决定了它捕捉声音细节的能力。想象麦克风是一只有耳朵的生物。高灵敏度麦克风像长着“超级顺风耳”的精灵&#xff0c;能听见花瓣飘落的声音、远处树叶的沙沙声&#xff0c;甚至你心跳的微弱震动。适合录音棚里捕捉歌手的…...

国产linux系统(银河麒麟,统信uos)使用 PageOffice 在线打开Word文件,并用前端对话框实现填空填表

不管是政府机关、公司企业&#xff0c;还是金融行业、教育行业等单位&#xff0c;在办公过程中都经常需要填写各种文书和表格&#xff0c;比如通知、报告、登记表、计划表、申请表等。这些文书和表格往往是用Word文件制作的模板&#xff0c;比方说一个通知模板中经常会有“关于…...