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

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)

二分查找是一种经典的搜索算法&#xff0c;广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素&#xff0c;减少了搜索的时间复杂度。本文将介绍在 C 和 Python 中内置的二分查找函数&#xff0c;让二分查找变得更加容易。 c lower_bound() 、upper_bound 定义…...

爬虫 — App 爬虫(二)

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

汽车电子相关术语

SOA SOA&#xff08;Service-Oriented Architecture&#xff0c;面向服务的架构&#xff09;是一种在计算机环境中设计、开发、部署和管理离散模型的方法。是由Garnter1996年提出的概念&#xff0c;将应用程序的不同功能单元&#xff08;称为服务&#xff09;进行拆分&#xf…...

Python 找出最大数

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

Spring Security 用了那么久,你对它有整体把控吗?

文章目录 1.Servlet Filter&#xff1a;守门人的角色2.DelegatingFilterProxy&#xff1a;桥接 Servlet 和 Spring 的神器3.FilterChainProxy&#xff1a;Spring Security 过滤器链的管家3.SecurityFilterChain&#xff1a;Security 过滤器的串绳4.Spring Security 中的过滤器机…...

vue+minio实现文件上传操作

vueminio实现文件上传操作 minio文件上传vueminio实现文件上传操作 minio文件上传 minio文件上传有两种方法&#xff1a; 第一种是通过ak&#xff0c;sk&#xff0c;调用minio的sdk putObject进行文件上传&#xff1b;该方法支持go&#xff0c;java&#xff0c;js等各种语言&…...

使用JavaScript实现无限滚动的方法

前言 在网页设计中&#xff0c;无限滚动是一种常见的交互方式&#xff0c;用户可持续地加载更多内容而无需刷新页面&#xff0c;提高用户体验。本文将介绍如何运用JavaScript实现无限滚动的效果&#xff0c;使网页能够自动加载更多数据&#xff0c;减轻用户加载新页的负担&…...

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

神经节苷脂抗体——博迈伦

神经节苷脂抗体是指人体免疫系统中产生的一类抗体&#xff0c;其主要作用是攻击神经节苷脂抗原物质。神经节苷脂是一种存在于神经细胞表面的重要分子&#xff0c;参与了神经细胞间的信号传导和细胞黏附等重要功能。正常情况下&#xff0c;人体免疫系统不会对神经节苷脂产生抗体…...

【Unity】简单的深度虚化shader

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

启动 React APP 后经历了哪些过程

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

带自动采集小说网站源码 小说听书网站源码 小说网站源码 带教程

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

MySQL学习笔记2

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

【python爬虫】—星巴克产品

文章目录 需求爬取星巴克产品以及图片&#xff0c;星巴克菜单 python爬虫爬取结果 需求 爬取星巴克产品以及图片&#xff0c;星巴克菜单 网页分析&#xff1a; 首先&#xff0c;需要分析星巴克官方网站的结构&#xff0c;了解菜单栏的位置、布局以及菜单项的标签或类名等信息…...

算法 矩阵最长递增路径-(递归回溯+动态规划)

牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置&#xff0c;max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时&#xff0c;使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时&#xff0c;如果dp[i][j]位…...

四、数学建模之图与网络模型

1.定义 2.例题及软件代码求解 一、定义 1.图和网络是相关概念 &#xff08;1&#xff09;图&#xff08;Graph&#xff09;&#xff1a;图是数学和计算机科学中的一个抽象概念&#xff0c;它由一组节点&#xff08;顶点&#xff09;和连接这些节点的边组成。图可以是有向的&…...

php在header增加key,sign,timestamp,实现鉴权

在PHP中&#xff0c;您可以通过在HTTP请求的Header中增加Key、Sign和Timestamp等信息来进行安全性鉴权。 以下是一种基本的思路和示例&#xff0c;用于说明如何实现这种鉴权机制&#xff1a; 生成Key和Sign&#xff1a; 服务端和客户端之间共享一个密钥&#xff08;Key&#x…...

Spring实例化源码解析之ConfigurationClassParser(三)

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

在 Substance Painter中实现Unity Standard Shader

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

第二证券:个人开证券账户要开户费吗?

随着互联网和移动端东西的遍及&#xff0c;越来越多的人开端涉足股票投资&#xff0c;开立证券账户也成为一个热门话题。但是&#xff0c;许多初学者或许会有疑问&#xff0c;个人开证券账户是否需求支付开户费呢&#xff1f;这个问题的答案并不是那么简略&#xff0c;需求考虑…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...