深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置
深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置
引言
二分查找,作为算法界的“常青树”,以其高效性和简洁性备受青睐。然而,许多初学者仅限于使用它查找单个元素,而对其进阶应用知之甚少。今天,我们就来剖析一个经典的二分查找变种——在排序数组中查找元素的第一个和最后一个位置。
这不仅是 LeetCode 上的经典问题(34. 在排序数组中查找元素的第一个和最后一个位置),也是面试高频考点。话不多说,直接上问题。
问题描述
给定一个按照升序排列的整数数组 nums
和一个目标值 target
,请你找到 target
在数组中的起始位置和结束位置。
如果数组中不存在 target
,返回 [-1, -1]
。
示例:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
直觉解法 vs. 二分查找
直觉解法: 既然数组是有序的,我们可以使用线性扫描,遍历数组一次找到 target
的首尾索引。代码如下:
# 线性扫描解法(O(n) 复杂度)
def searchRange(nums, target):if not nums:return [-1, -1]first, last = -1, -1for i in range(len(nums)):if nums[i] == target:if first == -1:first = ilast = ireturn [first, last]
这个方法简单直白,但时间复杂度是 O(n),对于大规模数据(如百万级别)并不高效。因此,我们需要一个更快的方法,而二分查找是我们的救星!
二分查找的延伸
思路解析
二分查找的核心在于“排除一半”,通常用于寻找某个特定的数。但在本题中,我们要找到 target
的边界(第一个和最后一个出现的位置)。
所以,我们需要两次二分查找:
- 第一次二分查找:找到
target
出现的第一个位置。 - 第二次二分查找:找到
target
出现的最后一个位置。
代码实现
# 二分查找解法(O(log n) 复杂度)
def searchRange(nums, target):def find_first(nums, target):left, right = 0, len(nums) - 1first = -1while left <= right:mid = (left + right) // 2if nums[mid] >= target: # 关键点:即使找到 target 也要继续向左逼近right = mid - 1else:left = mid + 1if nums[mid] == target:first = midreturn firstdef find_last(nums, target):left, right = 0, len(nums) - 1last = -1while left <= right:mid = (left + right) // 2if nums[mid] <= target: # 关键点:即使找到 target 也要继续向右逼近left = mid + 1else:right = mid - 1if nums[mid] == target:last = midreturn lastreturn [find_first(nums, target), find_last(nums, target)]
代码解析
find_first(nums, target)
负责找到target
第一次出现的位置。- 当
nums[mid] == target
时,不立即返回,而是继续向左逼近,缩小right
。
- 当
find_last(nums, target)
负责找到target
最后一次出现的位置。- 当
nums[mid] == target
时,不立即返回,而是继续向右逼近,扩大left
。
- 当
- 时间复杂度:每个二分查找都是
O(log n)
,所以总的时间复杂度是 O(log n)。
示例运行
print(searchRange([5,7,7,8,8,10], 8)) # 输出: [3, 4]
print(searchRange([5,7,7,8,8,10], 6)) # 输出: [-1, -1]
print(searchRange([], 0)) # 输出: [-1, -1]
为什么二分查找更优?
相较于线性扫描的 O(n)
,二分查找的 O(log n)
优势在数据量大的情况下尤为明显。
假设 nums
长度是 1,000,000
:
- 线性扫描:最坏情况下需遍历整个数组,即
1,000,000
次。 - 二分查找:每次查找最多
log_2(1,000,000) ≈ 20
次,大大减少了计算量。
总结 & 思考
- 二分查找不仅仅用于查找单个元素,还可以用来查找边界(最左、最右位置)。
- 找到
target
不能立即返回,而是要继续“逼近”目标边界。 - 掌握二分查找的变种(如:搜索插入位置、寻找峰值等),可以应对更多复杂问题。
这道题的本质在于二分查找的灵活性,希望这篇文章让你对它有更深入的理解!你是否还遇到过其他二分查找的应用呢?欢迎留言讨论!
相关文章:
深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置
深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置 引言 二分查找,作为算法界的“常青树”,以其高效性和简洁性备受青睐。然而,许多初学者仅限于使用它查找单个元素,而对其进阶应用知之甚少。今天…...
UE5中 Character、PlayerController、PlayerState、GameMode和GameState核心类之间的联动和分工·
1. GameMode 与 GameState 关系描述 GameMode:定义游戏规则和逻辑,控制游戏的开始、进行和结束。GameState:存储和同步全局游戏状态,如得分、时间、胜利条件等。 联动方式 GameMode初始化GameState:GameMode在游戏…...
使用Python获取并操作1688自定义API接口
在电子商务领域,1688作为国内领先的B2B平台,提供了丰富的API接口,允许开发者获取商品信息、店铺信息等。其中,custom接口允许开发者进行自定义操作,获取特定的数据。本文将详细介绍如何使用Python调用1688的custom接口…...
【AI】现代人工智能技术的应用与发展
引言 人工智能(AI)已经深入到我们生活的各个方面,涉及医疗、教育、交通、金融等众多领域。随着技术的不断发展,AI的应用和潜力也变得愈加广泛。本文将详细介绍人工智能的应用领域,探讨未来的发展趋势,并通…...
小程序渲染之谜:如何解决“加载中...”不消失的 Bug(glass-easel)
🎉 小程序渲染之谜:如何解决“加载中…”不消失的 Bug 🎉 引言 在小程序开发中,渲染问题总能让人抓狂。😫 这次,我遇到了一个奇怪的 bug:产品详情页的内容已经正常显示,但页面却一…...
C语言结构体全面解析 | 从入门到精通
📚 C语言结构体全面解析 | 从入门到精通 整理:算法练习生| 转载请注明出处 📑 目录 结构体的定义与使用结构体变量的参数传递结构体数组结构体指针typedef关键字结构体初始化 1️⃣ 结构体的定义与使用 为什么需要结构体? 当…...
Trae与Builder模式初体验
说明 下载的国际版:https://www.trae.ai/ 建议 要选新模型 效果 还是挺不错的,遇到问题反馈一下,AI就帮忙解决了,真是动动嘴(打打字就行了),做些小的原型效果或演示Demo很方便呀ÿ…...
麒麟服务器操作系统QT系列软件工具手册
QtCreator****功能介绍 QtCreator 概述 Qt Creator是跨平台的 Qt IDE, Qt Creator 是 Qt 被 [Nokia](https://baike.baidu.com/item/Nokia/264012" /t “_blank) 收购后推出的一款新的轻量级[集成开发环境](https://baike.baidu.com/item/集成开发环境/298524” /t “_…...
【HeadFirst系列之HeadFirstJava】第18天之深入理解原型模式:从问题到解决方案(含 Java 代码示例)
深入理解原型模式:从问题到解决方案(含 Java 代码示例) 在软件开发中,我们经常需要创建对象,而有些对象的创建成本较高或者结构较为复杂。如何在不破坏封装的前提下,高效地创建对象? 这正是**原…...
JetsonOrin源码安装部署PaddlePaddle
Jetson Orin 源码安装部署Paddle 部署环境 系统架构: Arm CUDA: 11.4 cmake: 3.18.0 python:3.8 注意环境中的版本问题,之前装onnxruntime的时候cmake被升级到了3.31.0,但是编译Paddle时会报错,因此特意降级回了官方推荐的3.18.0 具体环…...
入门到入土,Java学习 day20(多线程下)
void wait() 当前线程等待,直到被其他线程唤醒 void notify() 随机唤醒单个线程 void notifyAll() 唤醒所有线程 阻塞队列 在测试方法中创建带锁队列,然后在对象类中也创建队列但是不赋值,用构造方法将测试方法中的对象赋值 然后用put和t…...
【TCP】三次挥手,四次挥手详解--UDP和TCP协议详解
活动发起人小虚竹 想对你说: 这是一个以写作博客为目的的创作活动,旨在鼓励大学生博主们挖掘自己的创作潜能,展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴,那么,快来参加吧!…...
栈(LIFO)算法题
1.删除字符串中所有相邻的重复字符 注意,我们需要重复处理,而不是处理一次相邻的相同元素就结束了。对示例来说,如果只进行一次处理,结果为aaca,但是处理之后又出现了相邻的重复元素,我们还得继续处理&…...
印章/公章识别:PaddleX下的“Seal-Recognition”模型
最近做项目需要对印章进行识别,并提取其中的印章文字,又不希望这个模型太大,还要方便部署,于是乎这个模型是个不错的选择。 一、模型简介 “Seal-Recognition”模型是PaddleX旗下的一款模型(PaddleX 是基于飞桨框架构…...
从LLM出发:由浅入深探索AI开发的全流程与简单实践(全文3w字)
文章目录 第一部分:AI开发的背景与历史1.1 人工智能的起源与发展1.2 神经网络与深度学习的崛起1.3 Transformer架构与LLM的兴起1.4 当前AI开发的现状与趋势 第二部分:AI开发的核心技术2.1 机器学习:AI的基础2.1.1 机器学习的类型2.1.2 机器学…...
DeepSeek入门宝典——行业应用篇
大家好,我是吾鳴。 今天吾鳴要给大家分享一份由51CTO智能研究院出品的DeepSeek报告——《DeepSeek入门宝典——行业应用篇》。这份报告主要从DeepSeek核心能力、行业赋能与应用案例、合作伙伴与生态建设和学习资料与体系化方案做了详细的介绍,报告一共有…...
K8S学习之基础三十一:k8s中RBAC 的核心概念
Kubernetes (k8s) 中的 RBAC(Role-Based Access Control,基于角色的访问控制)是一种用于管理用户和服务账户对集群资源访问权限的机制。RBAC 允许管理员通过定义角色(Role)和角色绑定(RoleBindingÿ…...
JAVA数据库技术(一)
JDBC 简介 JDBC(Java Database Connectivity)是Java平台提供的一套用于执行SQL语句的Java API。它允许Java程序连接到数据库,并通过发送SQL语句来查询、更新和管理数据库中的数据。JDBC为不同的数据库提供了一种统一的访问方式,使…...
【Agent】OpenManus-Flow组件详细分析
1. Flow架构概述 OpenManus 的Flow组件实现了一个灵活的工作流管理系统,主要用于协调多个智能体的协作,以完成复杂任务。Flow组件的核心是基于计划的执行模型,它将任务分解为一系列步骤,然后逐步执行这些步骤,直到任务…...
MySQL环境安装详细教程(Windows/macOS/Linux)
摘要:本文详细介绍了在Windows、macOS和Linux三大操作系统下安装MySQL数据库的完整流程,帮助开发者快速搭建本地MySQL环境。 一、MySQL安装前准备 官网下载 访问MySQL官网 → 选择"Downloads" → 选择"MySQL Community (GPL) Downloads&…...
【人工智能基础2】人工神经网络、卷积神经网络基础、循环神经网络、长短时记忆网络
文章目录 三、人工神经网络1. 神经元感知模型2. 神经网络模型3. 学习规则:修改神经网络的权重和偏置反向传播算法(BP)优化器 - 梯度下降法 四、卷积神经网络基础(CNN)1. 基本原理2. 计算过程 五、循环神经网络(RNN&…...
如何查看windows系统的硬件环境(附方法
方法一:使用命令指示符查询 在“开始”菜单中搜索:命令指示符,并以管理员身份打开, 输入:systeminfo,就可以查看硬件、CPU、处理器等详细内容 systeminfo 方法二:在资源监视器中查看 按住 “…...
基于树莓派的水果分类系统(论文+源码)
针对小型农户的在水果加工销售环节中的分类需求,本文设计并实现了基于树莓派的视觉识别分类系统。本章根据所选水果的具体情况,简述系统各模块的实现方法,设计树莓派的程序算法,并选择合适的器件型号,开发所用的辅助工…...
Gemini Robotics:将人工智能带入物理世界
25年3月来自谷歌的技术报告“Gemini Robotics: Bringing AI into the Physical World”。 大型多模态模型的最新进展,已使数字领域出现卓越的通才能力,但将其转化为机器人等物理智体仍然是一项重大挑战。一般有用的机器人需要能够理解周围的物理世界&am…...
2.5[frontEnd]
requestAnimationFrame 是 浏览器原生 API,定义在 window 对象中,属于 Web API 的一部分。无需任何导入即可直接使用,其类型定义包含在 TypeScript 标准库中。 React 组件挂载时执行该 useEffect 初始化节流计时器 lastEmit 和 25ms 触发间隔…...
【动手学深度学习】#2线性神经网络
主要参考学习资料: 《动手学深度学习》阿斯顿张 等 著 【动手学深度学习 PyTorch版】哔哩哔哩跟李牧学AI 目录 2.1 线性回归2.1.1 线性回归的基本元素线性模型损失函数解析解随机梯度下降 2.1.3 最大似然估计 2.2 线性回归从零开始实现2.2.1 生成数据集2.2.2 读取数…...
C语言动态内存管理(上)
欢迎拜访:雾里看山-CSDN博客 本篇主题:C语言动态内存管理(上) 发布时间:2025.3.16 隶属专栏:C语言 目录 为什么需要动态内存管理静态分配的局限性动态分配的优势 动态内存函数malloc函数介绍函数使用 free函数介绍函数使用 calloc…...
图解多头注意力机制:维度变化一镜到底
目录 一、多头注意力机制概述二、代码实现1. pyTorch 实现2. tensorFlow实现 三、维度变化全流程详解1. 参数设定2. 维度变化流程图3. 关键步骤维度变化 四、关键实现细节解析1. 多头拆分与合并2. 注意力分数计算3. 掩码处理技巧 五、完整运行示例六、总结与常见问题1. 核心优势…...
Navicat如何查看密码
近期遇到需要将大部分已存储的navicat数据库转发给其他人,于是乎进行导出文件 奈何对方不用navicat,无法进行文件的导入从而导入链接 搜罗navicat的密码查看,大部分都为php代码解析 以下转载GitHub上看到的一个python代码解析的脚本 这里是对…...
第4节:分类任务
引入: 独热编码(one-hot):对于分类任务的输出,也就是是或不是某类的问题,采取独热编码的形式将y由一离散值转化为连续的概率分布,最大值所在下标为预测类 输入的处理:对于任意一张…...
EasyCVR安防视频汇聚平台助力工业园区构建“感、存、知、用”一体化智能监管体系
在现代工业园区的安全管理和高效运营中,视频监控系统扮演着不可或缺的角色。然而,随着园区规模的扩大和业务的复杂化,传统的视频监控系统面临着诸多挑战,如设备众多难以统一管理、数据存储分散、智能分析能力不足、信息利用率低下…...
计算机网络——DNS
一、什么是DNS? DNS(Domain Name System,域名系统) 是互联网的核心服务,负责将人类可读的域名(如 www.baidu.com)转换为机器可识别的 IP地址(如 14.119.104.254)。它像一…...
STC89C52单片机学习——第20节: [8-2]串口向电脑发送数据电脑通过串口控制LED
写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难,但我还是想去做! 本文写于:2025.03.15 51单片机学习——第20节: [8-2]串口向电脑发送数据&电脑通过串口控制LED 前言…...
1.5[hardware][day5]
Link类跳转指令可以拆分为两个部分,一个是跳转,即下一个PC的生成,如果将分支条件的比较放到译码级来进行,则这部分只涉及取值级和译码级流水;另一个是Link操作,简单来说就是写寄存器,这部则主要…...
Java 多线程编程:提升系统并发处理能力!
多线程是 Java 中实现并发任务执行的关键技术,能够显著提升程序在多核处理器上的性能以及处理多任务的能力。本文面向初级到中级开发者,从多线程的基本定义开始,逐步讲解线程创建、状态管理、同步机制、并发工具以及新兴的虚拟线程技术。每部…...
Mininet 的详细设计逻辑
Mininet 是一个轻量级网络仿真工具,其核心目标是在单台物理机上快速构建复杂的虚拟网络拓扑,支持 SDN(软件定义网络)和传统网络协议的实验与验证。其设计逻辑围绕 虚拟化、模块化 和 灵活性 展开,以下是其详细设计架构…...
原生微信小程序实现导航漫游(Tour)
效果: 小程序实现导航漫游 1、组件 miniprogram/components/tour/index.wxml <!--wxml--> <view class"guide" wx:if"{{showGuide}}"><view style"{{guideStyle}}" class"guide-box"><view class&quo…...
Spring(6)——Spring、Spring Boot 与 Spring MVC 的关系与区别
Spring、Spring Boot 与 Spring MVC 的关系与区别 1. 核心定位 Spring 定位:基础框架,提供 IoC(控制反转) 和 DI(依赖注入) 核心功能,管理对象生命周期及依赖关系。功能:支持事务管…...
神聖的綫性代數速成例題2. 行列式的性質
性質 1:行列式與它的轉置行列式相等: 設為行列式,為其轉置行列式,則。 性質 2:交換行列式的兩行 (列),行列式變號: 若行列式經過交換第行和第行得到行列式,則。 性質 3ÿ…...
ModelScope推理QwQ32B
文章目录 ModelScope推理QwQ32Bmodel_scope下载QwQ32BModelScope 调用QwQ-32B ModelScope推理QwQ32B 以下载 qwq32b 为例子 需要安装的 python 包 transformers4.49.0 accelerate>0.26.0 torch2.4.1 triton3.0.0 safetensors0.4.5可以使用 conda 创建一个虚拟环境安装 cond…...
使用unsloth进行grpo强化学习训练
说明 unsloth框架可以进行各种sft训练,包括lora和grpo训练。我参考官方方法,使用模型Qwen2.5-3B-Instruct和数据集gsm8k,写了一个grpo训练的例子。 代码 这个代码加载模型Qwen2.5-3B-Instruct和数据集gsm8k。训练完成后先保存lora模型然后…...
【c++】【智能指针】shared_ptr底层实现
【c】【智能指针】shared_ptr底层实现 智能指针之前已经写过了,但是考虑到不够深入,应该再分篇写写。 1 shared_ptr 1.1 shared_ptr 是什么 std::shared_ptr是一个类模板,它的对象行为像指针,但是它还能记录有多少个对象共享它…...
python拉取大视频导入deepseek大模型解决方案
使用Python拉取大视频并导入大模型,需要综合考虑数据获取、存储、处理和资源管理,确保高效稳定地处理大视频数据,同时充分利用大模型的性能,以下是分步方案及代码示例: --- 1. 分块下载大视频(避免内存溢出…...
【Python】面向对象
编程的两大特点 面向过程:着重于做什么面向对象( oop):着重于谁去做 python是面向对象语言,面向对象三大特点:封装、继承、多态 面向对象:便于代码管理,方便迭代更新。 新式类、经…...
leetcode日记(100)填充每个节点的下一个右侧节点指针
和层序遍历差不多的思路,将节点储存在队列里,一边取出节点一边放入取出节点的左右节点,直到队列空。 /* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NU…...
docker入门篇
使用docker可以很快部署相同的环境,这也是最快的环境构建,接下来就主要对docker中的基础内容进行讲解.Docker 是一个用于开发、交付和运行应用程序的开源平台,它可以让开发者将应用程序及其依赖打包到一个容器中,然后在任何环境中运行这个容器࿰…...
python语法
1. 前面先写import导入模块,完整的语法是: [from 模块名] import [模块 | 类 | 变量 | 函数 | *] [as 别名] 语法还可以是: from 模块名 import 功能名 如果import整个模块的话,需要用.功能名(),来用这个功能ÿ…...
Dify使用部署与应用实践
最近在研究AI Agent,发现大家都在用Dify,但Dify部署起来总是面临各种问题,而且我在部署和应用测试过程中也都遇到了,因此记录如下,供大家参考。Dify总体来说比较灵活,扩展性比较强,适合基于它做…...
微信小程序接入DeepSeek模型(火山方舟),并在视图中流式输出
引言: DeepSeek,作为一款先进的自然语言处理模型,以其强大的文本理解和生成能力著称。它能够处理复杂的文本信息,进行深度推理,并快速给出准确的回应。DeepSeek模型支持流式处理,这意味着它可以边计算边输…...
前端性能优化指标及优化方案
前端性能优化的核心目标是 提高页面加载速度、降低交互延迟、减少资源占用。常见的 Web 性能指标包括 LCP、FID、CLS、TTFB、TTI、FCP 等。 关键性能指标(Web Vitals) 指标优化方案 (1)LCP(Largest Contentful Paint&…...