python/C++二分查找库函数(lower_bound() 、upper_bound,bisect_left,bisect_right)
二分查找是一种经典的搜索算法,广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素,减少了搜索的时间复杂度。本文将介绍在 C++ 和 Python 中内置的二分查找函数,让二分查找变得更加容易。
c++
lower_bound() 、upper_bound
定义在<algorithm>
头文件中,
lower_bound 和 upper_bound 是 C++ STL 中与二分查找相关的两个非常有用的函数。它们都用于在有序容器中查找元素的位置。下面我将通过一个示例来详细讲解它们的用法。
假设我们有一个有序的整数数组 arr,如下所示:
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9};int target = 4;// 使用 lower_bound 查找目标值的第一个出现位置std::vector<int>::iterator lower = std::lower_bound(arr.begin(), arr.end(), target);// 使用 upper_bound 查找目标值的最后一个出现位置的下一个位置std::vector<int>::iterator upper = std::upper_bound(arr.begin(), arr.end(), target);// 输出结果std::cout << "数组中 " << target << " 的出现位置:" << std::endl;std::cout << "lower_bound 的结果:" << std::distance(arr.begin(), lower) << std::endl;std::cout << "upper_bound 的结果:" << std::distance(arr.begin(), upper) << std::endl;return 0;
}
在上述示例中,我们使用了 lower_bound 和 upper_bound 函数来查找目标值 4 在数组中的位置。下面是这两个函数的详细解释:
-
lower_bound:它返回一个迭代器,指向数组中第一个不小于目标值的元素。在我们的示例中,lower 将指向数组中第一个 4 的位置。
-
upper_bound:它返回一个迭代器,指向数组中第一个大于目标值的元素。在我们的示例中,upper 将指向数组中第一个大于 4 的元素位置。
请注意,如果目标值在数组中不存在,lower 和 upper 的差值将为零,因为它们将指向同一个位置。这两个函数在查找有序容器中的范围时非常有用,帮助我们精确定位元素的位置。
python
bisect_left
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect_left 函数在 Python 的 bisect 模块中用于在有序序列中查找目标值的插入位置,它接受四个参数:
a:表示有序序列,通常是一个列表。
x:表示要查找的目标值。
lo(可选):表示搜索范围的起始位置,默认为 0。
hi(可选):表示搜索范围的结束位置,默认为序列的长度。
下面是一个示例,演示了 bisect.bisect_left 函数的用法:
import bisectarr = [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
target = 4# 在整个序列中查找目标值的插入位置
index = bisect.bisect_left(arr, target)
print(f"在整个序列中查找 {target} 的插入位置:{index}")# 在指定范围内查找目标值的插入位置
lo = 2 # 搜索范围的起始位置
hi = 7 # 搜索范围的结束位置
index_range = bisect.bisect_left(arr, target, lo, hi)
print(f"在范围 [{lo}, {hi}] 内查找 {target} 的插入位置:{index_range}")
在上述示例中,首先我们在整个序列中查找目标值 4 的插入位置,然后在指定范围 [2, 7] 内查找 4 的插入位置。这两个插入位置的结果将告诉你如果将目标值插入到序列中,它应该出现在哪个位置。
bisect_right
bisect.bisect_right 函数与 bisect.bisect_left 函数非常类似,都用于在有序序列中查找目标值的插入位置。它们的区别在于,bisect_right 返回的位置是目标值插入后应该位于的右侧位置,而 bisect_left 返回的位置是目标值插入后应该位于的左侧位置。
相关文章:
python/C++二分查找库函数(lower_bound() 、upper_bound,bisect_left,bisect_right)
二分查找是一种经典的搜索算法,广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素,减少了搜索的时间复杂度。本文将介绍在 C 和 Python 中内置的二分查找函数,让二分查找变得更加容易。 c lower_bound() 、upper_bound 定义…...

爬虫 — App 爬虫(二)
目录 一、Appium介绍二、node.js 安装三、Java 的 SDK 安装以及配置1、安装步骤2、配置环境变量 四、安卓环境的配置1、配置环境变量 五、Appium 安装1、安装2、打开 APP3、使用 六、Appium 使用1、定位数据(方法一,不常用)2、定位数据&#…...

汽车电子相关术语
SOA SOA(Service-Oriented Architecture,面向服务的架构)是一种在计算机环境中设计、开发、部署和管理离散模型的方法。是由Garnter1996年提出的概念,将应用程序的不同功能单元(称为服务)进行拆分…...

Python 找出最大数
"""在输入的三个数中找出最大知识点:1、条件嵌套语句if/else2.字符串分割函数split()3、列表元素索引4、数据类型转换举一反三:1、如何控制只能输入三个数,否则重新输入2、如何避免输入无效字母"""# 定义一个变…...

Spring Security 用了那么久,你对它有整体把控吗?
文章目录 1.Servlet Filter:守门人的角色2.DelegatingFilterProxy:桥接 Servlet 和 Spring 的神器3.FilterChainProxy:Spring Security 过滤器链的管家3.SecurityFilterChain:Security 过滤器的串绳4.Spring Security 中的过滤器机…...
vue+minio实现文件上传操作
vueminio实现文件上传操作 minio文件上传vueminio实现文件上传操作 minio文件上传 minio文件上传有两种方法: 第一种是通过ak,sk,调用minio的sdk putObject进行文件上传;该方法支持go,java,js等各种语言&…...
使用JavaScript实现无限滚动的方法
前言 在网页设计中,无限滚动是一种常见的交互方式,用户可持续地加载更多内容而无需刷新页面,提高用户体验。本文将介绍如何运用JavaScript实现无限滚动的效果,使网页能够自动加载更多数据,减轻用户加载新页的负担&…...

html学习综合案例1
<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>个人简介</title> </head> <body>…...
神经节苷脂抗体——博迈伦
神经节苷脂抗体是指人体免疫系统中产生的一类抗体,其主要作用是攻击神经节苷脂抗原物质。神经节苷脂是一种存在于神经细胞表面的重要分子,参与了神经细胞间的信号传导和细胞黏附等重要功能。正常情况下,人体免疫系统不会对神经节苷脂产生抗体…...

【Unity】简单的深度虚化shader
【Unity】简单的深度虚化shader 实现效果 可以用于对地图场景边界的白模处理 实现方法 1.关键方法 UnityObjectToClipPos:将物体坐标转换为屏幕坐标 LinearEyeDepth:将屏幕坐标中的z值转换为实际的深度值 saturate:将值规范到0~1之间&a…...

启动 React APP 后经历了哪些过程
本文作者为 360 奇舞团前端开发工程师 前言 本文中使用的React版本为18,在摘取代码的过程中删减了部分代码,具体以源代码为准。 在React 18里,通过ReactDOM.createRoot创建根节点。并且通过调用原型链上的render来渲染。 本文主要是从以下两个…...

带自动采集小说网站源码 小说听书网站源码 小说网站源码 带教程
PTCMS可听书可下载的小说站源码 带自动采集和搭建视频教程 必装环境:Nginx(apache.iis也可),mysql,php5.6,memcached php5.6安装扩展memcache新建站点,注意新建时,PHP版本必须选择PHP5.6 安装教程 1.上传网站文件到网站目录&…...

MySQL学习笔记2
MySQL glibc版本安装: 下载相应的安装包。 学会查看mysql的官方文档: 1) 2)点击“Reference Manual”按钮: 3)选择5.7版本: 4)点击Installing MySQL on Unix/Linux Using Generic …...

【python爬虫】—星巴克产品
文章目录 需求爬取星巴克产品以及图片,星巴克菜单 python爬虫爬取结果 需求 爬取星巴克产品以及图片,星巴克菜单 网页分析: 首先,需要分析星巴克官方网站的结构,了解菜单栏的位置、布局以及菜单项的标签或类名等信息…...
算法 矩阵最长递增路径-(递归回溯+动态规划)
牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位…...

四、数学建模之图与网络模型
1.定义 2.例题及软件代码求解 一、定义 1.图和网络是相关概念 (1)图(Graph):图是数学和计算机科学中的一个抽象概念,它由一组节点(顶点)和连接这些节点的边组成。图可以是有向的&…...
php在header增加key,sign,timestamp,实现鉴权
在PHP中,您可以通过在HTTP请求的Header中增加Key、Sign和Timestamp等信息来进行安全性鉴权。 以下是一种基本的思路和示例,用于说明如何实现这种鉴权机制: 生成Key和Sign: 服务端和客户端之间共享一个密钥(Key&#x…...

Spring实例化源码解析之ConfigurationClassParser(三)
前言 上一章我们分析了ConfigurationClassPostProcessor的postProcessBeanDefinitionRegistry方法的源码逻辑,其中核心逻辑do while中调用parser.parse(candidates)方法,解析candidates中的候选配置类。然后本章我们主要分析ConfigurationClassParser的…...

在 Substance Painter中实现Unity Standard Shader
由于有需要在Substance Painter中显示什么样的效果,在Unity就要显示什么样的效果的需求,最近研究了几天,总算在Substance Painter中实现Unity standard的材质的渲染效果。具体效果如下: 在Unity中: Substance Painte…...

第二证券:个人开证券账户要开户费吗?
随着互联网和移动端东西的遍及,越来越多的人开端涉足股票投资,开立证券账户也成为一个热门话题。但是,许多初学者或许会有疑问,个人开证券账户是否需求支付开户费呢?这个问题的答案并不是那么简略,需求考虑…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...

【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...