【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 也慢慢的 开始跟进,截止到目前,商店的大部分应用都已经完成了 暗…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
