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

第二证券:个人开证券账户要开户费吗?
随着互联网和移动端东西的遍及,越来越多的人开端涉足股票投资,开立证券账户也成为一个热门话题。但是,许多初学者或许会有疑问,个人开证券账户是否需求支付开户费呢?这个问题的答案并不是那么简略,需求考虑…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...