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

【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(难度⭐⭐)(18)

1. 题目解析

Leetcode链接:34. 在排序数组中查找元素的第一个和最后一个位置

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

核心在于找到给定目标值所在的数组下标区间,设计一个O(logn)的算法。


2. 算法原理

寻找左边界思路:

目标:找到数组中第一个大于或等于目标值的元素的索引。

特点

  • 左边区间 [left, resLeft - 1] 的所有元素都小于 target
  • 右边区间(包括 resLeft[resLeft, right] 的所有元素都大于等于 target

二分查找步骤

  1. 初始化 left 和 right 为数组的开始和结束索引。
  2. 计算中间索引 mid(注意向下取整)。
  3. 根据 arr[mid] 与 target 的关系,调整 left 或 right 的值。
    • 如果 arr[mid] < target,则更新 left = mid + 1
    • 如果 arr[mid] >= target,则更新 right = mid
  4. 重复步骤 2 和 3,直到 left > right
  5. 返回 left 或 right(取决于具体实现)。

注意:当 right = mid 时,应向下取整,以防止死循环。

寻找右边界思路:

目标:找到数组中最后一个大于或等于目标值的元素的索引。

特点

  • 左边区间 [left, resRight] 的所有元素都小于等于 target
  • 右边区间 [resRight + 1, right] 的所有元素都大于 target

二分查找步骤

  1. 初始化 left 和 right 为数组的开始和结束索引。
  2. 计算中间索引 mid(注意向上取整)。
  3. 根据 arr[mid] 与 target 的关系,调整 left 或 right 的值。
    • 如果 arr[mid] <= target,则更新 left = mid
    • 如果 arr[mid] > target,则更新 right = mid - 1
  4. 重复步骤 2 和 3,直到 left > right
  5. 返回 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链接&#xff1a;34. 在排序数组中查找元素的第一个和最后一个位置 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 核心在于找到给定目标值所在的数组下标区间&#xff0c;设计一个O(logn)的算法。 2. 算法原…...

远程连接 vscode 出错 “远程主机可能不符合 glibc 和 libstdc++ VS Code 服务器的先决条件”

原因&#xff1a; vscode 版本是 1.86&#xff0c;服务器上的 glibc 和 libstdc 版本不满足 要求(2.28 和 3.4.25)。 解决&#xff1a; 1、下载 1.85.2&#xff0c;解压直接运行 Code.exe。 2、回退 Remote-ssh 到 0.107.1。 参考&#xff1a; vscode 1.86版本远程ssh不兼容旧…...

Maven入门:Java项目构建和管理的利器

Maven入门&#xff1a;Java项目构建和管理的利器 Maven 是一个项目管理和综合工具&#xff0c;它基于项目对象模型&#xff08;POM&#xff09;概念。Maven 可以管理项目的构建、报告和文档。以下是一篇介绍 Maven 配置和应用的教程文章。 Maven简介 Maven 使用其核心概念 POM…...

《游戏引擎架构》 -- 学习4

资源及文件系统 文件系统 游戏引擎的文件系统API通常提供以下功能&#xff1a; 搜需路径&#xff1a;是含一串路径的字符串&#xff0c;各路径之间以特殊字符&#xff08;如冒号或分号&#xff09;分隔&#xff0c;找文件时就会从这些路径进行搜寻。例如在命令行下执行程序&a…...

Wagtail安装运行并结合内网穿透实现公网访问本地网站界面

文章目录 前言1. 安装并运行Wagtail1.1 创建并激活虚拟环境 2. 安装cpolar内网穿透工具3. 实现Wagtail公网访问4. 固定的Wagtail公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xf…...

10分钟快速开始SkyWalking结合Springboot项目

10分钟快速开始SkyWalking结合Springboot项目 实习期间&#xff0c;公司让我去学习一下链路追踪如何集成到Springboot项目中。 为此有两个方案&#xff1a; 1.opentelementryjaegerprometheus opentelementry 收集器收集线上的metrics和traces&#xff0c;然后发送给jaeger和p…...

STM32—触摸键

目录 1 、 电路构成及原理图 2 、编写实现代码 3、代码讲解 4、烧录到开发板调试、验证代码 5、检验效果 此笔记基于朗峰 STM32F103 系列全集成开发板的记录。 1 、 电路构成及原理图 触摸键简单的了解就是一次电容的充放电过程。从原理图可以看出&#xff0c;触摸键 …...

python中字典(dict)原理及其操作

原理 Python中的字典&#xff08;Dictionary&#xff09;是一种基于哈希表&#xff08;Hash Table&#xff09;的实现&#xff0c;提供了高效的键值对&#xff08;Key-Value Pair&#xff09;存储和访问机制。了解字典的工作原理有助于更好地理解其性能特性以及为什么在某些情…...

​​​​​​​​​​​​​​.NET Core Web API实现微服务集群部署

​​​​​​​.NET Core Web API实现微服务集群部署 在.NET Core Web API中实现微服务集群部署通常涉及多个步骤&#xff0c;包括服务拆分、容器化、服务注册与发现、负载均衡等。以下是一个简化的步骤指南&#xff0c;用于在.NET Core中构建和部署微服务集群&#xff1a; 服…...

网络安全与信创产业发展:构建数字时代的护城河

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…...

外包干了3个月,技术倒退1年。。。

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…...

Unity发布webgl获取浏览器的URL

Unity发布webgl获取浏览器的URL Unity发布webgl之后获取浏览器的url 在unity中创建文件夹Plugins&#xff0c;然后添加添加文件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使用&#xff1a; Result 如果您不了解samber/mo库&#xff0c; 请先阅读上一篇 Option &#xff0c; 这篇讲述结构体Result的使用 Result和Option区别 samber/mo有了Option&#xff0c; 为什么还有Result呢? 我们先看看定义&#xff1a; Opt…...

Python 实现 CHO 指标计算(济坚指数):股票技术分析的利器系列(12)

Python 实现 CHO 指标计算(济坚指数&#xff09;&#xff1a;股票技术分析的利器系列&#xff08;12&#xff09; 介绍算法公式 代码rolling函数介绍核心代码计算 CHO 完整代码 介绍 CHO&#xff08;济坚指数&#xff09;是一种在金融领域中用于衡量市场波动性和风险的指数 先…...

MySQL的SQL语句

1.MySQL连接 连接命令一般是这样写的 mysql -h$ip -P$port -u$user -p比如:mysql -h127.0.0.1 -P3306 -uroot -p -h 指定连接的主机地址&#xff1b;-P 指定连接端口号&#xff1b;-u 指定用户名 -p指定用户名密码 2.SQL分类 DDL(Data Definition Language) 数据定义语言&…...

ABAP 发送带EXCEL邮件

前言 没啥特殊需求&#xff0c;就是有个库龄报表用户想整邮件发送 实现 用的最简单的XLS文件作为excel附件发送出去 观察XLS文件的纯文本格式&#xff0c;每列之间用TAB制表符分隔&#xff0c;每行之间用回车符分隔 思路也比较明确&#xff0c;在SAP中实现这种格式&#xf…...

Linux Nginx SSL 证书配置正确,扔展示不安全

Nginx SSL 配置 首先我能够确定自己的Nginx SSL是配置正确的&#xff1a; 问题展示 通过浏览器访问自己域名&#xff0c;点击不安全后查看证书&#xff0c;展示的证书并不是自己所配置的证书&#xff0c;如下&#xff1a; 通过curl -vvv https://域名访问返回的证书是过期…...

算法沉淀——动态规划之子数组、子串系列(上)(leetcode真题剖析)

算法沉淀——动态规划之子数组、子串系列 01.最大子数组和02.环形子数组的最大和03.乘积最大子数组04.乘积为正数的最长子数组长度 01.最大子数组和 题目链接&#xff1a;https://leetcode.cn/problems/maximum-subarray/、 给你一个整数数组 nums &#xff0c;请你找出一个具…...

Flutter GetX 之 暗黑模式

我们紧接上篇文章&#xff0c;今天继续讲解一下强大的 GetX 的另一个功能&#xff0c;就是 暗黑模式 &#xff0c;在iOS 13开始苹果的应用慢慢的都开始适配 暗黑模式&#xff0c;andr。oid 也慢慢的 开始跟进&#xff0c;截止到目前&#xff0c;商店的大部分应用都已经完成了 暗…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...