当前位置: 首页 > 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;商店的大部分应用都已经完成了 暗…...

语义分割实战:如何用Python快速计算mIoU和mAcc(附完整代码)

语义分割实战&#xff1a;Python高效计算mIoU与mAcc的工程化实现 在计算机视觉领域&#xff0c;语义分割模型的性能评估离不开mIoU&#xff08;平均交并比&#xff09;和mAcc&#xff08;平均准确率&#xff09;这两个核心指标。许多教程停留在理论公式层面&#xff0c;而实际项…...

2-1爬取豆瓣电影数据

数据来源网站&#xff1a;https://movie.douban.com/chart import requests import json import timedef fetch_douban():all_movies []start 0limit 20print("开始爬取豆瓣电影榜单")headers {"User-Agent": "Mozilla/5.0","Referer&…...

3步解决HEIC预览难题:面向Windows用户的高效缩略图工具

3步解决HEIC预览难题&#xff1a;面向Windows用户的高效缩略图工具 【免费下载链接】windows-heic-thumbnails Enable Windows Explorer to display thumbnails for HEIC files 项目地址: https://gitcode.com/gh_mirrors/wi/windows-heic-thumbnails 在数字影像管理中&…...

OpenClaw自动化测试:Qwen3-32B批量执行LeetCode题目

OpenClaw自动化测试&#xff1a;Qwen3-32B批量执行LeetCode题目 1. 为什么需要自动化编程能力测试 作为一名长期关注AI编程辅助工具的技术博主&#xff0c;我一直在寻找能够客观评估大模型编程能力的方法。传统的单次对话测试往往带有偶然性&#xff0c;无法系统性地反映模型…...

光阀的“第二曲线”:投影行业LCOS技术现状与发展趋势分析

1. 报告导读与核心摘要 在投影显示技术的版图中,LCoS(硅基液晶,Liquid Crystal on Silicon)长期处于一种微妙的位置:它拥有DLP无法比拟的画质潜力,却因成本和体积问题始终未能真正撼动DLP的市场地位。然而,2025-2026年行业展会上的一系列技术突破,正在改写这一格局。 …...

Periphery终极部署指南:Docker和Bazel构建的完整说明

Periphery终极部署指南&#xff1a;Docker和Bazel构建的完整说明 【免费下载链接】periphery A tool to identify unused code in Swift projects. 项目地址: https://gitcode.com/gh_mirrors/pe/periphery Periphery是一款强大的Swift代码分析工具&#xff0c;专门用于…...

从EWA Splatting到3DGS:一阶泰勒展开如何保住高斯的“椭圆”形状?

从EWA Splatting到3DGS&#xff1a;一阶泰勒展开如何保住高斯的“椭圆”形状&#xff1f; 在计算机图形学的演进历程中&#xff0c;三维高斯分布&#xff08;3D Gaussian&#xff09;的投影问题一直是个既基础又关键的挑战。想象一下&#xff0c;当你试图将一个完美的三维椭球投…...

语音转换完全上手:Retrieval-based Voice-Conversion-WebUI从入门到精通

语音转换完全上手&#xff1a;Retrieval-based Voice-Conversion-WebUI从入门到精通 【免费下载链接】Retrieval-based-Voice-Conversion-WebUI 语音数据小于等于10分钟也可以用来训练一个优秀的变声模型&#xff01; 项目地址: https://gitcode.com/GitHub_Trending/re/Retr…...

HUNYUAN-MT企业级Java集成指南:构建高并发翻译微服务

HUNYUAN-MT企业级Java集成指南&#xff1a;构建高并发翻译微服务 1. 引言 想象一下&#xff0c;你负责的电商平台刚刚接到一个来自海外的百万级订单&#xff0c;但商品详情、用户手册全是中文。市场团队急等着把上万页的产品资料翻译成十几种语言&#xff0c;时间窗口只有短短…...

告别低效写作:盘点2026年标杆级的AI论文网站

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文网站&#xff0c;覆盖选题构思、文献整理、内容生成、格式排版全流程&#xff0c;帮你高效搞定论文写作。 一、全流程王者&#xff1a;一站式搞定论文全链路&#xff08;一天定稿首选&#xff…...