整数二分算法
例题:
给定一个按照升序排列的长度为 n 的整数数组,以及 q个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0开始计数)。
如果数组中不存在该元素,则返回 -1 -1
。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。第二行包含 n 个整数(均在 1∼10000范围内),表示完整数组。接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1
。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
算法模板:
整数二分的本质不是单调性,只要可将区间依据是否满足某种性质一分为二,就可以用二分
bool check(int x) {} //检查x是否满足某种性质//区间[l, r]被划分为[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r) {while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}//区间[l, r]被划分为[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r) {while (l < r) {int mid = (l + r + 1) >> 1; //因为整数/2存在向下取整问题,如果这里不加1,更新时会出现l = mid = l的情况【如l = r - 1时】会陷入死循环 if (check(mid)) l = mid; else r = mid - 1;}return l;
}
区间如何更新?
参考题解
/*整数二分算法*/
#include <iostream>
#include <vector>using namespace std;int main () {int n, q; //数组长度和询问个数cin >> n >> q;vector<int> array (n);for(int i = 0; i < n; i++) {cin >> array[i];}while(q--) {int query;cin >> query;int l = 0, r = n - 1;while(l < r) {int mid = (l + r) >> 1;if(array[mid] >= query) { //找起始位置时,将性质定义为>=x r = mid;}else {l = mid + 1;}}if(array[l] != query) {cout << "-1 -1" << '\n';continue; }cout << l << ' ';l = 0, r = n - 1;while(l < r) {int mid = (l + r + 1) >> 1;if(array[mid] <= query) { //找结束位置时,将性质定义为<=x l = mid;}else {r = mid - 1;}}cout << l << '\n';}return 0;
}
总结
重点在于画图想清楚要找的分界点应该使用什么性质,以这道题为例,刚开始一直想着用<query来找,但就感觉这样不太对劲,画图后才清晰地理解为什么要用>=query
参考:AcWing关于二分的讲解
相关文章:
整数二分算法
例题: 给定一个按照升序排列的长度为 n 的整数数组,以及 q个查询。 对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0开始计数)。 如果数组中不存在该元素,则返回 -1 -1。 输入格式 第一行…...
【java】this关键字
在 Java 中,this 是一个特殊的关键字,它代表当前对象的引用。简单来说,this 指向当前正在调用方法或构造函数的对象。this 关键字的主要作用是解决变量名冲突、访问当前对象的成员变量或方法,以及在构造函数中调用其他构造函数。 …...
LD_PRELOAD 绕过 disable_function 学习
借助这位师傅的文章来学习通过LD_PRELOAD来绕过disable_function的原理 【PHP绕过】LD_PRELOAD bypass disable_functions_phpid绕过-CSDN博客 感谢这位师傅的贡献 介绍 静态链接: (1)举个情景来帮助理解: 假设你要搬家&#x…...
计算机毕业设计Hadoop+Spark+DeepSeek-R1大模型民宿推荐系统 hive民宿可视化 民宿爬虫 大数据毕业设计(源码+文档+PPT+讲解)
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
MySQL后端返回给前端的时间变了(时区问题)
问题:MySQL里的时间例如为2025-01-10 21:19:30,但是返回到前端就变成了2025-01-10 13:19:30,会出现小时不一样或日期变成隔日的问题 一般来说设计字段时会使用datetime字段类型,这是一种用于时间的字段类型,而这个类型…...
Apache Doris:一款高性能的实时数据仓库
Apache Doris 是一款基于 MPP 架构的高性能、实时分析型数据库。它以高效、简单和统一的特性著称,能够在亚秒级的时间内返回海量数据的查询结果。Doris 既能支持高并发的点查询场景,也能支持高吞吐的复杂分析场景。 Apache Doris 最初是百度广告报表业务…...
【量化-什么是信息?怎么有效的学习?关键字摘取】
到底什么是信息呢?我们怎么衡量信息的价值与多少呢?今天,我们就来说说这个问题。 怎么量化信息? 信息,只有量化了才能被准确地讨论,而量化的方法就和事件发生的概率密切相关。或者说得直白一些࿰…...
Java之异常体系
异常:异常就是代表程序出现问题 异常的继承体系: Error:严重异常,内存溢出等 其他异常:编译时异常:编译阶段就要进行处理的异常(提醒程序员检查本地信息) RuntimeException&#…...
网络运维学习笔记(DeepSeek优化版)002网工初级(HCIA-Datacom与CCNA-EI)子网划分与协议解析
文章目录 子网划分与协议解析1. VLSM与CIDR技术解析1.1 VLSM(Variable Length Subnetwork Mask,可变长子网掩码)1.2 CIDR(Classless Inter-Domain Routing,无类域间路由) 2. 子网划分方法与计算2.1 常规划分…...
【Linux知识】Linux上从源码编译到软件安装全过程详细说明
文章目录 **1. 下载源码****(1) 使用 wget 或 curl 下载****(2) 解压源码** **2. 配置编译环境****(1) 执行 ./configure 脚本**常见参数说明: **3. 编译源码****(1) 执行 make** **4. 安装软件****(1) 执行 make install****(2) 自定义安装路径** **5. 验证安装***…...
【尝试使用python调用Seismic unix】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、代码总结 前言 提示:这里可以添加本文要记录的大概内容: 使用seismic unix尝试建立界面,首先想到使用pyqt,…...
JSON Web Token在登陆中的使用
JWT(JSON Web Token)是一种开放标准(RFC 7519),用于在网络应用环境间安全地传递声明。它的主要用途是身份验证和信息交换。在微服务架构中,JWT 作为认证机制非常常见,特别是与 API 网关结合使用…...
CSS滚动条原理与自定义样式指南,CSS滚动条样式失效,滚动条样式无效,-webkit-scrollbar无效,overflow不显示滚动条
滚动内容形成的必要条件 CSS Overflow属性解析 MDN官方文档-Overflow属性 菜鸟教程-Overflow属性 overflow 属性控制内容溢出元素框时在对应的元素区间内是否添加滚动条。 值描述visible默认值。内容不会被修剪,会呈现在元素框之外。hidden内容会被修剪…...
陀螺匠·企业助手v1.8 产品介绍
陀螺匠企业助手是一套采用Laravel 9框架结合Swoole高性能协程服务与Vue.js前端技术栈构建的新型智慧企业管理与运营系统。该系统深度融合了客户管理、项目管理、审批流程自动化以及低代码开发平台,旨在为企业提供一站式、数字化转型的全方位解决方案,助力…...
【数据结构】(11) Map 和 Set
一、Map 和 Set 的简介 1、Set 和 Map Map 和 Set 是集合类框架学习的最后一部分。Map 和 Set 都是接口,需要通过 TreeSet、HashSet 和 TreeMap、HashMap 实例化。注意,Set 实现了 Collection,Map 并没有。 Set 存放的是键(Key&a…...
DeepSeek 提示词:高效的提示词设计
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编…...
【Redis】在Java中以及Spring环境下操作Redis
Java环境下: 1.创建maven 项目 2.导入依赖 <!-- redis --><dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version>4.3.2</version></dependency> 此处使用的是Jedis&…...
Linux红帽:RHCSA认证知识讲解(二)配置网络与登录本地远程Linux主机
Linux红帽:RHCSA认证知识讲解(二)配置网络与登录本地远程Linux主机 前言一、使用命令行(nmcli 命令)配置网络,配置主机名第一步第二步修改主机名称 二、使用图形化界面(nmtui 命令)配…...
新数据结构(13)——I/O
字符流 字符输入流(Reader) 字符输入流用于从数据源(如文件、字符串等)读取字符数据。Reader 是所有字符输入流的抽象基类。 常用实现类 FileReader 用于从文件中读取字符数据。 InputStreamReader 将字节流转换为字符流&…...
C语言学习,希尔排序
C语言,希尔排序是插入排序的一种,也称为递减增量排序。通过比较距离较远的元素,然后逐渐缩小间隔,直到整个数组变成有序的。这种排序方法减少了插入排序,大数据集的移动次数,提高了效率。 示例:…...
Powershell Install deepseek
前言 deepseekAI助手。它具有聊天机器人功能,可以与用户进行自然语言交互,回答问题、提供建议和帮助解决问题。DeepSeek 的特点包括: 强大的语言理解能力:能够理解和生成自然语言,与用户进行流畅的对话。多领域知识&…...
22、《Spring Boot消息队列:RabbitMQ延迟队列与死信队列深度解析》
Spring Boot消息队列实战:RabbitMQ延迟队列与死信队列深度解析 引言 在现代分布式系统中,消息队列承担着解耦、削峰填谷和异步通信的重要职责。本文将深入探讨Spring Boot与RabbitMQ的整合应用,重点解析延迟队列与死信队列的实现原理及实战…...
性能测试项目实战
项目介绍和部署 项目背景 轻商城项目是一个现在流行的电商项目。我们需要综合评估该项目中各个关键接口的性能,并给出优化建议,以满足项目上线后的性能需要。 项目功能架构 前台商城:购物车、订单、支付、优惠券等 后台管理系统:商…...
LabVIEW中显微镜下位移误差的畸变
在显微实验中,位移台通过电机驱动探针进行微米级精确移动,配合显微镜和相机实时观察探针的位置。然而,实验中发现,当电机移动相同的物理距离时,图像中探针的像素位移量存在显著的非线性偏差。经测试,电机的…...
Spark MLlib中的机器学习算法及其应用场景
Spark MLlib是Apache Spark框架中的一个机器学习库,提供了丰富的机器学习算法和工具,用于处理和分析大规模数据。以下是Spark MLlib中的机器学习算法及其应用场景的详细描述: 一、Spark MLlib中的机器学习算法 分类算法: 逻辑回…...
Angular 中获取 DOM 节点的几种方法
文章目录 1. 使用ViewChild获取单个 DOM 节点2. 使用ViewChildren获取多个 DOM 节点3. 使用ElementRef直接访问 DOM4. 使用Renderer2操作 DOM5. 总结 在 Angular 开发中,虽然框架鼓励我们通过组件和模板来操作 DOM,但在某些情况下,直接访问和…...
R Excel 文件:高效数据处理的利器
R Excel 文件:高效数据处理的利器 在数据分析领域,R语言因其强大的统计分析和可视化功能而备受推崇。而R Excel文件,作为R语言与Excel的桥梁,使得数据在R和Excel之间的高效转换成为可能。本文将详细介绍R Excel文件的概念、应用场景以及操作方法。 一、R Excel文件的概念…...
手撕跳表/数据结构
昨天leetcode每日一题是跳表,之前学redis就没去写跳表,这次就逃不过了。 这里使用了len数组,来表示每个数字之间的间隔,方便复杂的查询功能。 主要问题有 为什么len数组记录的是数字之间的间隔,不是每一层从头到尾…...
在 Vue 中处理跨域请求:全面解析与实践指南
在 Vue 中处理跨域请求:全面解析与实践指南 在现代 Web 开发的复杂生态中,跨域请求(CORS)如同一个无处不在的难题,时刻考验着开发者的技术能力。当我们构建基于 Vue.js 的前端应用时,这一问题尤为凸显。因为…...
爬虫与反爬-Ja3指纹风控(Just a moment...)处理方案及参数说明
概述:本文将针对Ja3 指纹检测风控进行处理,举例了一个案例并使用两种不同的破解方案进行突破,同时深入了解指纹间不同字符所代表的含义 指纹检测背景: 1、每一个设备、软件都有独属于自己的设备信息、版本号、加密算法、椭圆算法…...
WPF-Avalonia实践一两个页面的相关传递
文章目录 注册两个ViewModel关联-Interaction在 Avalonia 框架中的 Interaction作用目的典型的使用场景显示对话框:文件操作:定义交互属性示例代码视图层处理交互总结例子-实现两个界面信息传递Interaction注册在主VIEWModel中注册异步方法按钮主viewModel对应的显示xaml-使用…...
无人机实战系列(三)本地摄像头+远程GPU转换深度图
这篇文章将结合之前写的两篇文章 无人机实战系列(一)在局域网内传输数据 和 无人机实战系列(二)本地摄像头 Depth-Anything V2 实现了以下功能: 本地笔记本摄像头发布图像 远程GPU实时处理(无回传&#…...
LeetCode:数组异或操作
数组异或操作 描述 给你两个整数,n 和 start 。 数组 nums 定义为:nums[i] start 2*i(下标从 0 开始)且 n nums.length 。 请返回 nums 中所有元素按位异或(XOR)后得到的结果。 示例 1:…...
【前端】Axios AJAX Fetch
不定期更新,建议关注收藏点赞。 目录 AxiosAJAXCORS 允许跨域请求 Fetch Axios axios 是一个基于 Promise 的 JavaScript HTTP 客户端,用于浏览器和 Node.js 中发送 HTTP 请求。它提供了一个简单的 API 来发起请求,并处理请求的结果。axios …...
C++ 继承与运算符重载的简单练习
1.长方形的继承类 #include <iostream> #include <cstring> #include <cstdlib> #include <unistd.h> #include <sstream> #include <vector> #include <memory>using namespace std; class AB{ private:int a;int …...
pycharm技巧--鼠标滚轮放大或缩小 Pycharm 字体大小
1、鼠标滚轮调整字体 设置 Ctrl 鼠标滚轮调整字体大小 备注: 第一个是活动窗口,即缩放当前窗口 第二个是所有编辑器窗口,即缩放所有窗口的字体 2、插件 汉化包: Chinese Simplified 包...
deepseek 导出导入模型(docker)
前言 实现导出导入deepseek 模型。deepseek 安装docker下参考 docker 导出模型 实际生产环境建议使用docker-compose.yml进行布局,然后持久化ollama模型数据到本地参考 echo "start ollama" docker start ollama#压缩容器内文件夹,然后拷贝…...
STM32——HAL库开发笔记21(定时器2—输出比较)(参考来源:b站铁头山羊)
本文主要讲述输出比较及PWM信号相关知识。 一、概念 所谓输出比较,就是通过单片机的定时器向外输出精确定时的方波信号。 1.1 PWM信号 PWM信号即脉冲宽度调制信号。PWM信号的占空比 (高电压 所占周期 / 整个周期) * 100% 。所以PWM信号…...
【报错解决】vue打开界面报错Uncaught SecurityError: Failed to construct ‘WebSocket‘
问题描述: vue运行时正常,但是打开页面后报错 Uncaught SecurityError: Failed to construct WebSocket: An insecure WebSocket connection may not be initiated from a page loaded over HTTPS. 解决方案: 在项目列表中的public下的ind…...
【初探数据结构】时间复杂度和空间复杂度
💬 欢迎讨论:在阅读过程中有任何疑问,欢迎在评论区留言,我们一起交流学习! 👍 点赞、收藏与分享:如果你觉得这篇文章对你有帮助,记得点赞、收藏,并分享给更多对数据结构感…...
将DeepSeek接入vscode的N种方法
接入deepseek方法一:cline 步骤1:安装 Visual Studio Code 后,左侧导航栏上点击扩展。 步骤2:搜索 cline,找到插件后点击安装。 步骤3:在大模型下拉菜单中找到deep seek,然后下面的输入框输入你在deepseek申请的api key,就可以用了 让deepseek给我写了一首关于天气的…...
《TransMamba:一种混合Transformer-Mamba网络用于单图像去雨》学习笔记
paper:2409.00410 GitHub:sunshangquan/TransMamba 目录 摘要 1、介绍 2、相关工作 2.1 单图像去雨 2.2 视觉Transformer 2.3 光谱域中的Transformer 2.4 光谱域中的图像恢复 2.5 视觉Mamba 3、方法 3.1 整体网络架构 3.2 光谱域变换块&am…...
危化品经营单位安全管理人员的职责及注意事项
危化品经营单位安全管理人员肩负着保障经营活动安全的重要责任,以下是其主要职责及注意事项: 职责 1. 安全制度建设与执行:负责组织制定本单位安全生产规章制度、操作规程和生产安全事故应急救援预案,确保这些制度符合国家相关法…...
安装Redis并把Redis设置成windows下的服务然后进行Redis实例演示
目录 (一)安装Redis (二)Redis设置成windows下的服务 1、把redis设置成windows下的服务 2、设置服务命令 (三)Redis实例演示 1、Redis插入数据 2、Redis修改数据 3、Redis删除数据 4、Redis查询数…...
基于 Python 的项目管理系统开发
基于 Python 的项目管理系统开发 一、引言 在当今快节奏的工作环境中,有效的项目管理对于项目的成功至关重要。借助信息技术手段开发项目管理系统,能够显著提升项目管理的效率和质量。Python 作为一种功能强大、易于学习且具有丰富库支持的编程语言&…...
牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)
文章目录 牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)A. 夹心饼干B. C. 食堂大作战(思维)D. 小苯的排列计数(差分、树状数组)E. 和和(大根堆,前缀和)F. 怎么写线性SPJ &…...
【python】解析自动化脚本文件并按照=测试周期=存储记录
【python】连接Jira获取token以及jira对象 【python】解析自动化脚本文件并按照测试周期存储记录 【python】向Jira推送自动化用例执行成功 【python】向Jira测试计划下,附件中增加html测试报告 将已编写的自动化测试用例按照jira号解析出来,并按照测试计…...
一种简单有效的分析qnx+android智能座舱项目中的画面闪烁的方法(8155平台)
在智能座舱项目的开发过程中,画面闪烁问题是一个常见但棘手的挑战。由于这些闪烁现象往往转瞬即逝,传统的分析工具如截图、录屏或dump图层等方法难以捕捉和定位问题根源。针对这一难题,本文介绍了一种较为有效的分析方法,能够帮助…...
架构师论文《论湖仓一体架构及其应用》
软考论文-系统架构设计师 摘要 作为某省级商业银行数据中台建设项目技术负责人,我在2020年主导完成了从传统数据仓库向湖仓一体架构的转型。针对日益增长的支付流水、用户行为埋点及信贷审核影像文件等多模态数据处理需求,原有系统存在存储成本激增、实…...
一篇文章学懂Vuex
一、基于VueCli自定义创建项目 233 344 二、Vuex 初始准备 建项目的时候把vuex勾选上就不用再yarn add vuex3了 store/index.js // 这里面存放的就是vuex相关的核心代码 import Vuex from vuex import Vue from vue// 插件安装 Vue.use(Vuex)// 创建仓库(空仓库…...