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…...

第二证券:个人开证券账户要开户费吗?
随着互联网和移动端东西的遍及,越来越多的人开端涉足股票投资,开立证券账户也成为一个热门话题。但是,许多初学者或许会有疑问,个人开证券账户是否需求支付开户费呢?这个问题的答案并不是那么简略,需求考虑…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...