【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(难度⭐⭐)(18)
1. 题目解析
Leetcode链接:34. 在排序数组中查找元素的第一个和最后一个位置

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
核心在于找到给定目标值所在的数组下标区间,设计一个O(logn)的算法。
2. 算法原理
寻找左边界思路:
目标:找到数组中第一个大于或等于目标值的元素的索引。
特点:
- 左边区间
[left, resLeft - 1]的所有元素都小于target。 - 右边区间(包括
resLeft)[resLeft, right]的所有元素都大于等于target。
二分查找步骤:
- 初始化
left和right为数组的开始和结束索引。 - 计算中间索引
mid(注意向下取整)。 - 根据
arr[mid]与target的关系,调整left或right的值。- 如果
arr[mid] < target,则更新left = mid + 1。 - 如果
arr[mid] >= target,则更新right = mid。
- 如果
- 重复步骤 2 和 3,直到
left > right。 - 返回
left或right(取决于具体实现)。
注意:当 right = mid 时,应向下取整,以防止死循环。
寻找右边界思路:
目标:找到数组中最后一个大于或等于目标值的元素的索引。
特点:
- 左边区间
[left, resRight]的所有元素都小于等于target。 - 右边区间
[resRight + 1, right]的所有元素都大于target。
二分查找步骤:
- 初始化
left和right为数组的开始和结束索引。 - 计算中间索引
mid(注意向上取整)。 - 根据
arr[mid]与target的关系,调整left或right的值。- 如果
arr[mid] <= target,则更新left = mid。 - 如果
arr[mid] > target,则更新right = mid - 1。
- 如果
- 重复步骤 2 和 3,直到
left > right。 - 返回
right或left(取决于具体实现)。
注意:当 right = mid 时,应向上取整,以防止死循环。
通过合理地调整 left 和 right 的值,二分查找可以高效地找到左边界和右边界。
3. 代码编写
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, begin = -1, end = -1, mid;//找到区间左边界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{begin = mid;right--;//right区间左移,使得mid左移,直到到达左区间边界,此时right正好和left重合}}left = 0, right = nums.size() - 1;//找到区间有边界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{end = mid;left++;//left区间右移,使得mid右移,直到到达又区间边界,此时left正好和right重合}}return {begin,end};}
};
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~
相关文章:
【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(难度⭐⭐)(18)
1. 题目解析 Leetcode链接:34. 在排序数组中查找元素的第一个和最后一个位置 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 核心在于找到给定目标值所在的数组下标区间,设计一个O(logn)的算法。 2. 算法原…...
远程连接 vscode 出错 “远程主机可能不符合 glibc 和 libstdc++ VS Code 服务器的先决条件”
原因: vscode 版本是 1.86,服务器上的 glibc 和 libstdc 版本不满足 要求(2.28 和 3.4.25)。 解决: 1、下载 1.85.2,解压直接运行 Code.exe。 2、回退 Remote-ssh 到 0.107.1。 参考: vscode 1.86版本远程ssh不兼容旧…...
Maven入门:Java项目构建和管理的利器
Maven入门:Java项目构建和管理的利器 Maven 是一个项目管理和综合工具,它基于项目对象模型(POM)概念。Maven 可以管理项目的构建、报告和文档。以下是一篇介绍 Maven 配置和应用的教程文章。 Maven简介 Maven 使用其核心概念 POM…...
《游戏引擎架构》 -- 学习4
资源及文件系统 文件系统 游戏引擎的文件系统API通常提供以下功能: 搜需路径:是含一串路径的字符串,各路径之间以特殊字符(如冒号或分号)分隔,找文件时就会从这些路径进行搜寻。例如在命令行下执行程序&a…...
Wagtail安装运行并结合内网穿透实现公网访问本地网站界面
文章目录 前言1. 安装并运行Wagtail1.1 创建并激活虚拟环境 2. 安装cpolar内网穿透工具3. 实现Wagtail公网访问4. 固定的Wagtail公网地址 正文开始前给大家推荐个网站,前些天发现了一个巨牛的 人工智能学习网站, 通俗易懂,风趣幽默…...
10分钟快速开始SkyWalking结合Springboot项目
10分钟快速开始SkyWalking结合Springboot项目 实习期间,公司让我去学习一下链路追踪如何集成到Springboot项目中。 为此有两个方案: 1.opentelementryjaegerprometheus opentelementry 收集器收集线上的metrics和traces,然后发送给jaeger和p…...
STM32—触摸键
目录 1 、 电路构成及原理图 2 、编写实现代码 3、代码讲解 4、烧录到开发板调试、验证代码 5、检验效果 此笔记基于朗峰 STM32F103 系列全集成开发板的记录。 1 、 电路构成及原理图 触摸键简单的了解就是一次电容的充放电过程。从原理图可以看出,触摸键 …...
python中字典(dict)原理及其操作
原理 Python中的字典(Dictionary)是一种基于哈希表(Hash Table)的实现,提供了高效的键值对(Key-Value Pair)存储和访问机制。了解字典的工作原理有助于更好地理解其性能特性以及为什么在某些情…...
.NET Core Web API实现微服务集群部署
.NET Core Web API实现微服务集群部署 在.NET Core Web API中实现微服务集群部署通常涉及多个步骤,包括服务拆分、容器化、服务注册与发现、负载均衡等。以下是一个简化的步骤指南,用于在.NET Core中构建和部署微服务集群: 服…...
网络安全与信创产业发展:构建数字时代的护城河
✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua,在这里我会分享我的知识和经验。&#x…...
外包干了3个月,技术倒退1年。。。
先说情况,大专毕业,18年通过校招进入湖南某软件公司,干了接近6年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...
Unity发布webgl获取浏览器的URL
Unity发布webgl获取浏览器的URL Unity发布webgl之后获取浏览器的url 在unity中创建文件夹Plugins,然后添加添加文件UnityGetBrowserURL.jslib var GetUrlFunc {//获取地址栏的URLStringReturnValueFunction: function () {var returnStr window.top.location.hre…...
StarRocks实战——多维分析场景与落地实践
目录 一、OLAP 系统历史背景 1.1 历史背景与痛点 1.2 组件诉求 二、StarRocks 的特点和优势 2.1 极致的查询性能 2.2 丰富的导入方式 2.3 StarRocks 的优势特点 三、多维分析的运用场景 3.1 实时计算场景 / 家长监控中心 3.2 实时更新模型选择 3.2.1 更新模型UNIQU…...
golang 函数式编程库samber/mo使用: Result
golang 函数式编程库samber/mo使用: Result 如果您不了解samber/mo库, 请先阅读上一篇 Option , 这篇讲述结构体Result的使用 Result和Option区别 samber/mo有了Option, 为什么还有Result呢? 我们先看看定义: Opt…...
Python 实现 CHO 指标计算(济坚指数):股票技术分析的利器系列(12)
Python 实现 CHO 指标计算(济坚指数):股票技术分析的利器系列(12) 介绍算法公式 代码rolling函数介绍核心代码计算 CHO 完整代码 介绍 CHO(济坚指数)是一种在金融领域中用于衡量市场波动性和风险的指数 先…...
MySQL的SQL语句
1.MySQL连接 连接命令一般是这样写的 mysql -h$ip -P$port -u$user -p比如:mysql -h127.0.0.1 -P3306 -uroot -p -h 指定连接的主机地址;-P 指定连接端口号;-u 指定用户名 -p指定用户名密码 2.SQL分类 DDL(Data Definition Language) 数据定义语言&…...
ABAP 发送带EXCEL邮件
前言 没啥特殊需求,就是有个库龄报表用户想整邮件发送 实现 用的最简单的XLS文件作为excel附件发送出去 观察XLS文件的纯文本格式,每列之间用TAB制表符分隔,每行之间用回车符分隔 思路也比较明确,在SAP中实现这种格式…...
Linux Nginx SSL 证书配置正确,扔展示不安全
Nginx SSL 配置 首先我能够确定自己的Nginx SSL是配置正确的: 问题展示 通过浏览器访问自己域名,点击不安全后查看证书,展示的证书并不是自己所配置的证书,如下: 通过curl -vvv https://域名访问返回的证书是过期…...
算法沉淀——动态规划之子数组、子串系列(上)(leetcode真题剖析)
算法沉淀——动态规划之子数组、子串系列 01.最大子数组和02.环形子数组的最大和03.乘积最大子数组04.乘积为正数的最长子数组长度 01.最大子数组和 题目链接:https://leetcode.cn/problems/maximum-subarray/、 给你一个整数数组 nums ,请你找出一个具…...
Flutter GetX 之 暗黑模式
我们紧接上篇文章,今天继续讲解一下强大的 GetX 的另一个功能,就是 暗黑模式 ,在iOS 13开始苹果的应用慢慢的都开始适配 暗黑模式,andr。oid 也慢慢的 开始跟进,截止到目前,商店的大部分应用都已经完成了 暗…...
Vue项目中使用/deep/报错?手把手教你用::v-deep完美解决样式问题
Vue样式穿透难题:从/deep/到::v-deep的优雅升级指南 在Vue生态中,样式作用域管理一直是开发者们津津乐道的话题。当你在使用第三方UI库时,是否遇到过这样的尴尬:明明在本地开发环境调试好的样式,打包后却神秘失效&…...
2024版idea引入lombok总是报错解决方法
在创建SpringBoot文件时不勾选lombok,然后自己手动导入lombok并指定版本玛德这idea的SpringBoot中导入lombok后我使用Data总是说我的get和set方法有毛病,一怒之下我直接就是疯狂搜如何解决lombok引用问题,结果不是让我去勾选一个东西就是让我…...
Vue中实现动态标签页的切换优化与状态管理
1. 动态标签页的核心需求与实现思路 在后台管理系统这类多页面应用中,动态标签页几乎是标配功能。想象一下你正在使用某电商后台,同时开着商品管理、订单处理和用户分析三个页面,这时候标签页的流畅切换和状态保持就显得尤为重要。 我经历过一…...
带标注的交通工具分类数据集,17334张原始图片,识别率92.4%,可识别汽车,公共汽车,自行车,摩托车,支持yolo,coco json,pascal voc xml格式
带标注的交通工具分类数据集,17334张原始图片,识别率92.4%,可识别汽车,公共汽车,自行车,摩托车,支持yolo,coco json,pascal voc xml格式 模型训练指标参数: …...
在RK3576开发板上手把手编译并运行你的第一个MPP编码程序(含VSCode配置避坑)
在RK3576开发板上从零构建MPP编码开发环境的完整指南 1. 开发环境准备与交叉编译工具链配置 对于嵌入式开发者而言,RK3576开发板的MPP开发环境搭建需要从基础工具链开始。不同于x86平台的开发,我们需要特别注意交叉编译环境的配置细节。 首先需要获取适用…...
高效PDF处理:用PDF Arranger实现极简文档管理
高效PDF处理:用PDF Arranger实现极简文档管理 【免费下载链接】pdfarranger Small python-gtk application, which helps the user to merge or split PDF documents and rotate, crop and rearrange their pages using an interactive and intuitive graphical int…...
Abp要落地DDD重要的一步
要用到实体之间的依赖关系,也就是聚合根,否则每个实体一个仓储,光一个服务注入就十几个仓储,玩锤子...
程序员视角:五笔输入法98版为何更适合代码编写?
程序员视角:五笔输入法98版为何更适合代码编写? 在程序员的世界里,效率就是生命。从IDE的选择到快捷键的配置,每一个细节都可能影响编码的速度和质量。而作为中文开发者,输入法的选择往往被忽视——直到你发现自己在输…...
Elasticsearch IK 分词器远程词典
一、背景 在使用 Elasticsearch IK 分词器进行中文检索时,默认词库往往无法覆盖业务中的专业词汇(如:知识库、RAG架构、向量检索等)。 如果不进行扩展,这些词可能被错误拆分,导致: 检索结果不准…...
Llama-3.2V-11B-cot部署详解:自动修复视觉权重加载致命Bug全过程
Llama-3.2V-11B-cot部署详解:自动修复视觉权重加载致命Bug全过程 1. 项目概述 Llama-3.2V-11B-cot是基于Meta Llama-3.2V-11B-cot多模态大模型开发的高性能视觉推理工具,专为双卡RTX 4090环境深度优化。本工具通过自动修复视觉权重加载等核心Bug&#…...
