二分查找篇——在排序数组中查找元素的第一个和最后一个位置【LeetCode】

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

一、算法逻辑(逐步通顺讲解每一步思路)

该算法用于在一个升序排列的数组 nums 中查找某个目标值 target第一个出现的位置和最后一个出现的位置

✅ 1️⃣ 定义 lower_bound 函数

def lower_bound(self, nums: List[int], target: int) -> int:left, right = -1, len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] >= target:right = midelse:left = midreturn right
  • 这个函数返回的是第一个大于等于 target 的索引位置
  • 使用的是左闭右开区间 [left+1, right) 的二分写法,可以避免边界处理错误。
  • 循环终止时,right 就是第一个满足 nums[right] >= target 的位置。

✅ 2️⃣ 查找目标值的起始位置

start = self.lower_bound(nums, target)
  • 如果 nums[start] != target 或者 start == len(nums),说明数组中不存在该元素,直接返回 [-1, -1]

✅ 3️⃣ 查找目标值的结束位置

end = self.lower_bound(nums, target + 1) - 1
  • 我们通过查找 target + 1 的第一个位置,再减 1,就得到了 target 的最后一个位置。
  • 因为数组是有序的,所以 target + 1 第一次出现之前的所有元素都是 target

✅ 4️⃣ 返回结果

return [start, end]

二、核心点总结

利用两次二分查找精准定位范围

  • 使用两次「lower_bound」分别找到起始位置和结束位置,避免了线性扫描,效率高。

巧妙的“target + 1”技巧

  • 不需要额外编写一个 upper_bound 函数,只需将目标值加一,即可复用 lower_bound 找出右边界。

适合面试高频题型

  • 本题是典型的二分查找变形题,考察对边界条件的理解和对二分思想的灵活运用。

可扩展性强

  • 此种思路也可推广到其他变种问题,如:统计某数字在排序数组中出现的次数(剑指 Offer 题)等。
class Solution:def lower_bound(self, nums:List[int], target:int)-> int:left, right = -1, len(nums)while left+1 < right:mid = (left+right)//2if nums[mid]>=target:right = midelse:left = midreturn rightdef searchRange(self, nums: List[int], target: int) -> List[int]:start = self.lower_bound(nums, target)if start==len(nums) or nums[start] != target:return [-1,-1]end = self.lower_bound(nums, target+1)-1return [start, end]

三、时间复杂度分析

✅ 每次调用 lower_bound 是一个标准的二分查找过程:

  • 时间复杂度为 O(log n)

✅ 整体算法执行了两次二分查找:

  • 总体时间复杂度为 O(log n)

四、空间复杂度分析

✅ 整个过程中没有使用任何额外的数据结构:

  • 所有变量都是常数级的局部变量

✅ 空间复杂度为 O(1)


✅ 总结一句话

这段算法通过两次二分查找定位目标值的起始与结束位置,巧妙利用 target + 1 技巧避免重复编写 upper_bound,具有高效、简洁、稳定的特点,是解决有序数组中查找范围类问题的经典解法之一,非常适合作为面试准备的重点内容。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/news/913729.shtml
繁体地址,请注明出处:http://hk.pswp.cn/news/913729.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【深度学习新浪潮】AI在材料力学领域的研究进展一览

一、材料力学的研究范畴 材料力学是固体力学的核心分支,聚焦于材料在载荷作用下的变形、失效规律及性能优化,其核心任务是揭示材料的强度、刚度和稳定性机制。具体研究内容包括: 基本力学行为:分析杆、梁、轴等结构在拉伸、压缩、弯曲、扭转等载荷下的应力分布与应变响应。…

WPF之命令

命令的定义&#xff1a;命令与事件的区别&#xff1a;命令是具有约束性的。命令还可以控制接收者"先做校验&#xff0c;再保存&#xff0c;再关闭"。命令&#xff1a;WPF的命令&#xff0c;实际上就是实现了ICommand接口的类&#xff0c;平时使用最多的是RoutedComma…

百度文心一言开源大模型ERNIE-4.5-0.3B-PT深度测评

号外号外&#xff01;6月30号&#xff0c;百度文心一言官宣开源ERNIE 4.5大模型&#xff01;&#xff01;&#xff01; 一收到这个消息&#xff0c;博主就立马从GitCode拉了个模型&#xff0c;本地私有化部署体验了一下&#xff0c;一个字&#xff0c;酷&#xff01; 鉴于绝大…

零基础,使用Idea工具写一个邮件报警程序

打开idea&#xff0c;创建一个project打开文件目录下的pom.xml文件&#xff0c;添加下面的内容安装依赖&#xff0c;等待下载完成<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId> &…

字体 Unicode 区块字符展示 PDF 生成器

Unicode 字体字符集可视化工具 - 代码介绍 项目概述 这个工具是一个用于分析和可视化字体文件中包含的 Unicode 字符的实用程序&#xff0c;能够扫描指定字体文件&#xff0c;提取其中包含的所有 Unicode 字符&#xff0c;并按 Unicode 区块分类生成 PDF 文档&#xff0c;直观展…

第4章:实战项目一 打造你的第一个AI知识库问答机器人 (RAG)

各位老铁&#xff0c;欢迎来到我们专栏的第一个实战项目。 在过去的三个章节里&#xff0c;我们已经完成了所有的理论储备和环境搭建。我们理解了LLM的本质&#xff0c;掌握了Prompt Engineering的要领&#xff0c;洞悉了Embedding和向量数据库的魔力&#xff0c;并且熟悉了La…

身份证识别api-便捷生活与安全社会的双重保障

身份证识别技术是人工智能和图像处理领域的杰出产物之一&#xff0c;正逐步渗透到我们生活的方方面面。而最直观的作用就是简化身份证验证流程。现如今&#xff0c;无论是银行开户、酒店入住还是政务办理、线上支付&#xff0c;都需要输入 身份证信息进行身份验证&#xff0c;传…

跨国企业进入中国市场:如何利用亚马逊云科技文档 MCP 服务器解决区域差异问题

业务场景 想象一下&#xff0c;您是一家美国科技公司的 IT 架构师&#xff0c;公司刚刚决定将业务扩展到中国市场。作为技术负责人&#xff0c;您需要规划如何将现有的基于亚马逊云科技的应用迁移到中国区域。然而&#xff0c;您很快发现中国区的云服务环境与您熟悉的全球区域…

WPF使用WebBrowser 解决href标签target=_blank在浏览器窗口打开新链接而非窗体内部打开的问题

前言 最近在WPF中使用WebBrowser控件显示网页的时候遇到一个问题,由于网页里面有大规模的连接标签使用了target=_blank的属性,导致打开的网页不是在我们的程序内部,而是调用系统浏览器打开了我们的网页内容,这种情况非常的影响用户体验。于是就有了这篇文章内容。本文将详细…

制作MikTex本地包可用于离线安装包

MikTex安装包版本是basic-miktex-24.1-x64.exe。注&#xff1a;basic版本表示只安装MikTex基本包&#xff0c;不安装全部包。在能够联网的电脑上安装MikTex软件后&#xff0c;可以按以下步骤制作本地包库。一、制作本地包库1、新建一个文件夹&#xff0c;比如在D盘新建miktex-l…

Redis基础的介绍与使用(一)(Redis简介以及Redis下载和安装)

0 引言 本系列用于和大伙儿一起入门Redis&#xff0c;主要包括Redis的下载&#xff0c;分别在终端&#xff0c;图形显示界面以及JAVA代码中进行使用&#xff0c;适合给需要快速了解Redis是什么以及上手使用的朋友们&#xff0c;希望我用最简单的语言来讲清楚相关内容&#xff…

七牛云C++开发面试题及参考答案

智能指针的原理及应用场景是什么&#xff1f; 智能指针是 C 中用于管理动态分配内存的工具&#xff0c;其核心原理是通过 RAII&#xff08;资源获取即初始化&#xff09;技术&#xff0c;将堆内存的生命周期与对象的生命周期绑定&#xff0c;从而避免手动管理内存带来的内存泄…

【Python办公】Excel横板表头转竖版通用工具(GUI版本)横向到纵向的数据重构

目录 专栏导读前言项目概述功能特性技术栈核心代码解析1. 类结构设计2. 界面布局设计3. 滚动列表实现4. 数据转换核心逻辑5. 预览功能实现设计亮点1. 用户体验优化2. 技术实现优势3. 代码结构优势使用场景扩展建议总结完整代码结尾专栏导读 🌸 欢迎来到Python办公自动化专栏—…

C#项目 在Vue/React前端项目中 使用使用wkeWebBrowser引用并且内部使用iframe网页外链 页面部分白屏

如果是使用wkeWebBrowser的引用方式 非常有可能是版本问题导致的 问题分析 1. wkeWebBrowser 的局限性 不支持或不完全支持 ES6 语法&#xff08;如 let, const, Promise, async/await&#xff09; 缺少对现代 Web API 的支持&#xff08;如 Intl, fetch, WebSocket&#xff0…

系统架构设计师论文分享-论微服务架构

我的软考历程 摘要 2023年2月&#xff0c;我所在的公司通过了研发纱线MES系统的立项&#xff0c;该系统为国内纱线工厂提供SAAS服务&#xff0c;旨在提高纱线工厂的数字化和智能化水平。我在该项目中担任系统架构设计师一职&#xff0c;负责该项目的架构设计工作。本文结合我…

The History of Big Data

数据洪流悄然重塑世界的进程中&#xff0c;大数据的历史是技术迭代与需求驱动的交响。从 2003 年分布式系统雏形初现&#xff0c;到 Hadoop 掀起开源浪潮&#xff0c;再到 Spark、容器化技术与深度学习的接力革新&#xff0c;以及 Hadoop 生态的兴衰起落&#xff0c;大数据发展…

【JS逆向基础】数据分析之正则表达式

前言&#xff1a;前面介绍了关于JS逆向所需的基本知识&#xff0c;比如前端三件套等&#xff0c;从这里开始就要进入到数据分析的范围内了&#xff0c;当然对于一些小白而言一些基本的知识还是需要知道的&#xff0c;比如正则&#xff0c;XPATNY与BS4&#xff1b;三个内容用三篇…

Mac mini 高性价比扩容 + Crossover 游戏实测 全流程手册

Mac mini 高性价比扩容 Crossover 游戏实测 全流程手册 本文将图文并茂地指导你如何&#xff1a; 为 M4 Mac mini 外置扩容&#xff08;绿联 USB4 硬盘盒 致态 TiPlus7100&#xff09;安装并配置 Crossover/Whisky 运行 Windows 应用实测游戏运行性能、诊断常见异常一、准备工…

【PyTorch】PyTorch中torch.nn模块的卷积层

PyTorch深度学习总结 第七章 PyTorch中torch.nn模块的卷积层 文章目录PyTorch深度学习总结前言一、torch.nn模块1. 模块的基本组成部分1.1 层&#xff08;Layers&#xff09;1.2 损失函数&#xff08;Loss Functions&#xff09;1.3 激活函数&#xff08;Activation Functions…

Rust简洁控制流:if let与let else高效编程指南

文章目录Rust简洁控制流&#xff1a;if let与let else高效编程指南&#x1f3af; if let&#xff1a;专注单一匹配场景&#x1f4a1; if let核心优势&#xff1a;&#x1f504; if let与else搭配使用&#x1f680; let else&#xff1a;错误处理与提前返回&#x1f48e; let el…