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

深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置

深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置

引言

二分查找,作为算法界的“常青树”,以其高效性和简洁性备受青睐。然而,许多初学者仅限于使用它查找单个元素,而对其进阶应用知之甚少。今天,我们就来剖析一个经典的二分查找变种——在排序数组中查找元素的第一个最后一个位置。

这不仅是 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边界(第一个和最后一个出现的位置)。

所以,我们需要两次二分查找:

  1. 第一次二分查找:找到 target 出现的第一个位置
  2. 第二次二分查找:找到 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)]

代码解析

  1. find_first(nums, target) 负责找到 target 第一次出现的位置。
    • nums[mid] == target 时,不立即返回,而是继续向左逼近,缩小 right
  2. find_last(nums, target) 负责找到 target 最后一次出现的位置。
    • nums[mid] == target 时,不立即返回,而是继续向右逼近,扩大 left
  3. 时间复杂度:每个二分查找都是 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 次,大大减少了计算量。

总结 & 思考

  1. 二分查找不仅仅用于查找单个元素,还可以用来查找边界(最左、最右位置)
  2. 找到 target 不能立即返回,而是要继续“逼近”目标边界
  3. 掌握二分查找的变种(如:搜索插入位置、寻找峰值等),可以应对更多复杂问题

这道题的本质在于二分查找的灵活性,希望这篇文章让你对它有更深入的理解!你是否还遇到过其他二分查找的应用呢?欢迎留言讨论!

相关文章:

深入剖析二分查找的延伸:在排序数组中查找元素的第一个和最后一个位置

深入剖析二分查找的延伸&#xff1a;在排序数组中查找元素的第一个和最后一个位置 引言 二分查找&#xff0c;作为算法界的“常青树”&#xff0c;以其高效性和简洁性备受青睐。然而&#xff0c;许多初学者仅限于使用它查找单个元素&#xff0c;而对其进阶应用知之甚少。今天…...

UE5中 Character、PlayerController、PlayerState、GameMode和GameState核心类之间的联动和分工·

1. GameMode 与 GameState 关系描述 GameMode&#xff1a;定义游戏规则和逻辑&#xff0c;控制游戏的开始、进行和结束。GameState&#xff1a;存储和同步全局游戏状态&#xff0c;如得分、时间、胜利条件等。 联动方式 GameMode初始化GameState&#xff1a;GameMode在游戏…...

使用Python获取并操作1688自定义API接口

在电子商务领域&#xff0c;1688作为国内领先的B2B平台&#xff0c;提供了丰富的API接口&#xff0c;允许开发者获取商品信息、店铺信息等。其中&#xff0c;custom接口允许开发者进行自定义操作&#xff0c;获取特定的数据。本文将详细介绍如何使用Python调用1688的custom接口…...

【AI】现代人工智能技术的应用与发展

引言 人工智能&#xff08;AI&#xff09;已经深入到我们生活的各个方面&#xff0c;涉及医疗、教育、交通、金融等众多领域。随着技术的不断发展&#xff0c;AI的应用和潜力也变得愈加广泛。本文将详细介绍人工智能的应用领域&#xff0c;探讨未来的发展趋势&#xff0c;并通…...

小程序渲染之谜:如何解决“加载中...”不消失的 Bug(glass-easel)

&#x1f389; 小程序渲染之谜&#xff1a;如何解决“加载中…”不消失的 Bug &#x1f389; 引言 在小程序开发中&#xff0c;渲染问题总能让人抓狂。&#x1f62b; 这次&#xff0c;我遇到了一个奇怪的 bug&#xff1a;产品详情页的内容已经正常显示&#xff0c;但页面却一…...

C语言结构体全面解析 | 从入门到精通

&#x1f4da; C语言结构体全面解析 | 从入门到精通 整理&#xff1a;算法练习生| 转载请注明出处 &#x1f4d1; 目录 结构体的定义与使用结构体变量的参数传递结构体数组结构体指针typedef关键字结构体初始化 1️⃣ 结构体的定义与使用 为什么需要结构体&#xff1f; 当…...

Trae与Builder模式初体验

说明 下载的国际版&#xff1a;https://www.trae.ai/ 建议 要选新模型 效果 还是挺不错的&#xff0c;遇到问题反馈一下&#xff0c;AI就帮忙解决了&#xff0c;真是动动嘴&#xff08;打打字就行了&#xff09;&#xff0c;做些小的原型效果或演示Demo很方便呀&#xff…...

麒麟服务器操作系统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 代码示例)

深入理解原型模式&#xff1a;从问题到解决方案&#xff08;含 Java 代码示例&#xff09; 在软件开发中&#xff0c;我们经常需要创建对象&#xff0c;而有些对象的创建成本较高或者结构较为复杂。如何在不破坏封装的前提下&#xff0c;高效地创建对象&#xff1f; 这正是**原…...

JetsonOrin源码安装部署PaddlePaddle

Jetson Orin 源码安装部署Paddle 部署环境 系统架构: Arm CUDA: 11.4 cmake: 3.18.0 python:3.8 注意环境中的版本问题&#xff0c;之前装onnxruntime的时候cmake被升级到了3.31.0&#xff0c;但是编译Paddle时会报错&#xff0c;因此特意降级回了官方推荐的3.18.0 具体环…...

入门到入土,Java学习 day20(多线程下)

void wait() 当前线程等待&#xff0c;直到被其他线程唤醒 void notify() 随机唤醒单个线程 void notifyAll() 唤醒所有线程 阻塞队列 在测试方法中创建带锁队列&#xff0c;然后在对象类中也创建队列但是不赋值&#xff0c;用构造方法将测试方法中的对象赋值 然后用put和t…...

【TCP】三次挥手,四次挥手详解--UDP和TCP协议详解

活动发起人小虚竹 想对你说&#xff1a; 这是一个以写作博客为目的的创作活动&#xff0c;旨在鼓励大学生博主们挖掘自己的创作潜能&#xff0c;展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴&#xff0c;那么&#xff0c;快来参加吧&#xff01…...

栈(LIFO)算法题

1.删除字符串中所有相邻的重复字符 注意&#xff0c;我们需要重复处理&#xff0c;而不是处理一次相邻的相同元素就结束了。对示例来说&#xff0c;如果只进行一次处理&#xff0c;结果为aaca&#xff0c;但是处理之后又出现了相邻的重复元素&#xff0c;我们还得继续处理&…...

印章/公章识别:PaddleX下的“Seal-Recognition”模型

最近做项目需要对印章进行识别&#xff0c;并提取其中的印章文字&#xff0c;又不希望这个模型太大&#xff0c;还要方便部署&#xff0c;于是乎这个模型是个不错的选择。 一、模型简介 “Seal-Recognition”模型是PaddleX旗下的一款模型&#xff08;PaddleX 是基于飞桨框架构…...

从LLM出发:由浅入深探索AI开发的全流程与简单实践(全文3w字)

文章目录 第一部分&#xff1a;AI开发的背景与历史1.1 人工智能的起源与发展1.2 神经网络与深度学习的崛起1.3 Transformer架构与LLM的兴起1.4 当前AI开发的现状与趋势 第二部分&#xff1a;AI开发的核心技术2.1 机器学习&#xff1a;AI的基础2.1.1 机器学习的类型2.1.2 机器学…...

DeepSeek入门宝典——行业应用篇

大家好&#xff0c;我是吾鳴。 今天吾鳴要给大家分享一份由51CTO智能研究院出品的DeepSeek报告——《DeepSeek入门宝典——行业应用篇》。这份报告主要从DeepSeek核心能力、行业赋能与应用案例、合作伙伴与生态建设和学习资料与体系化方案做了详细的介绍&#xff0c;报告一共有…...

K8S学习之基础三十一:k8s中RBAC 的核心概念

Kubernetes (k8s) 中的 RBAC&#xff08;Role-Based Access Control&#xff0c;基于角色的访问控制&#xff09;是一种用于管理用户和服务账户对集群资源访问权限的机制。RBAC 允许管理员通过定义角色&#xff08;Role&#xff09;和角色绑定&#xff08;RoleBinding&#xff…...

JAVA数据库技术(一)

JDBC 简介 JDBC&#xff08;Java Database Connectivity&#xff09;是Java平台提供的一套用于执行SQL语句的Java API。它允许Java程序连接到数据库&#xff0c;并通过发送SQL语句来查询、更新和管理数据库中的数据。JDBC为不同的数据库提供了一种统一的访问方式&#xff0c;使…...

【Agent】OpenManus-Flow组件详细分析

1. Flow架构概述 OpenManus 的Flow组件实现了一个灵活的工作流管理系统&#xff0c;主要用于协调多个智能体的协作&#xff0c;以完成复杂任务。Flow组件的核心是基于计划的执行模型&#xff0c;它将任务分解为一系列步骤&#xff0c;然后逐步执行这些步骤&#xff0c;直到任务…...

MySQL环境安装详细教程(Windows/macOS/Linux)

摘要&#xff1a;本文详细介绍了在Windows、macOS和Linux三大操作系统下安装MySQL数据库的完整流程&#xff0c;帮助开发者快速搭建本地MySQL环境。 一、MySQL安装前准备 官网下载 访问MySQL官网 → 选择"Downloads" → 选择"MySQL Community (GPL) Downloads&…...

【人工智能基础2】人工神经网络、卷积神经网络基础、循环神经网络、长短时记忆网络

文章目录 三、人工神经网络1. 神经元感知模型2. 神经网络模型3. 学习规则:修改神经网络的权重和偏置反向传播算法&#xff08;BP&#xff09;优化器 - 梯度下降法 四、卷积神经网络基础&#xff08;CNN&#xff09;1. 基本原理2. 计算过程 五、循环神经网络&#xff08;RNN&…...

如何查看windows系统的硬件环境(附方法

方法一&#xff1a;使用命令指示符查询 在“开始”菜单中搜索&#xff1a;命令指示符&#xff0c;并以管理员身份打开&#xff0c; 输入&#xff1a;systeminfo&#xff0c;就可以查看硬件、CPU、处理器等详细内容 systeminfo 方法二&#xff1a;在资源监视器中查看 按住 “…...

基于树莓派的水果分类系统(论文+源码)

针对小型农户的在水果加工销售环节中的分类需求&#xff0c;本文设计并实现了基于树莓派的视觉识别分类系统。本章根据所选水果的具体情况&#xff0c;简述系统各模块的实现方法&#xff0c;设计树莓派的程序算法&#xff0c;并选择合适的器件型号&#xff0c;开发所用的辅助工…...

Gemini Robotics:将人工智能带入物理世界

25年3月来自谷歌的技术报告“Gemini Robotics: Bringing AI into the Physical World”。 大型多模态模型的最新进展&#xff0c;已使数字领域出现卓越的通才能力&#xff0c;但将其转化为机器人等物理智体仍然是一项重大挑战。一般有用的机器人需要能够理解周围的物理世界&am…...

2.5[frontEnd]

requestAnimationFrame 是 浏览器原生 API&#xff0c;定义在 window 对象中&#xff0c;属于 Web API 的一部分。无需任何导入即可直接使用&#xff0c;其类型定义包含在 TypeScript 标准库中。 React 组件挂载时执行该 useEffect 初始化节流计时器 lastEmit 和 25ms 触发间隔…...

【动手学深度学习】#2线性神经网络

主要参考学习资料&#xff1a; 《动手学深度学习》阿斯顿张 等 著 【动手学深度学习 PyTorch版】哔哩哔哩跟李牧学AI 目录 2.1 线性回归2.1.1 线性回归的基本元素线性模型损失函数解析解随机梯度下降 2.1.3 最大似然估计 2.2 线性回归从零开始实现2.2.1 生成数据集2.2.2 读取数…...

C语言动态内存管理(上)

欢迎拜访&#xff1a;雾里看山-CSDN博客 本篇主题&#xff1a;C语言动态内存管理(上) 发布时间&#xff1a;2025.3.16 隶属专栏&#xff1a;C语言 目录 为什么需要动态内存管理静态分配的局限性动态分配的优势 动态内存函数malloc函数介绍函数使用 free函数介绍函数使用 calloc…...

图解多头注意力机制:维度变化一镜到底

目录 一、多头注意力机制概述二、代码实现1. pyTorch 实现2. tensorFlow实现 三、维度变化全流程详解1. 参数设定2. 维度变化流程图3. 关键步骤维度变化 四、关键实现细节解析1. 多头拆分与合并2. 注意力分数计算3. 掩码处理技巧 五、完整运行示例六、总结与常见问题1. 核心优势…...

Navicat如何查看密码

近期遇到需要将大部分已存储的navicat数据库转发给其他人&#xff0c;于是乎进行导出文件 奈何对方不用navicat&#xff0c;无法进行文件的导入从而导入链接 搜罗navicat的密码查看&#xff0c;大部分都为php代码解析 以下转载GitHub上看到的一个python代码解析的脚本 这里是对…...

第4节:分类任务

引入&#xff1a; 独热编码&#xff08;one-hot&#xff09;&#xff1a;对于分类任务的输出&#xff0c;也就是是或不是某类的问题&#xff0c;采取独热编码的形式将y由一离散值转化为连续的概率分布&#xff0c;最大值所在下标为预测类 输入的处理&#xff1a;对于任意一张…...

EasyCVR安防视频汇聚平台助力工业园区构建“感、存、知、用”一体化智能监管体系

在现代工业园区的安全管理和高效运营中&#xff0c;视频监控系统扮演着不可或缺的角色。然而&#xff0c;随着园区规模的扩大和业务的复杂化&#xff0c;传统的视频监控系统面临着诸多挑战&#xff0c;如设备众多难以统一管理、数据存储分散、智能分析能力不足、信息利用率低下…...

计算机网络——DNS

一、什么是DNS&#xff1f; DNS&#xff08;Domain Name System&#xff0c;域名系统&#xff09; 是互联网的核心服务&#xff0c;负责将人类可读的域名&#xff08;如 www.baidu.com&#xff09;转换为机器可识别的 IP地址&#xff08;如 14.119.104.254&#xff09;。它像一…...

STC89C52单片机学习——第20节: [8-2]串口向电脑发送数据电脑通过串口控制LED

写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难&#xff0c;但我还是想去做&#xff01; 本文写于&#xff1a;2025.03.15 51单片机学习——第20节: [8-2]串口向电脑发送数据&电脑通过串口控制LED 前言…...

1.5[hardware][day5]

Link类跳转指令可以拆分为两个部分&#xff0c;一个是跳转&#xff0c;即下一个PC的生成&#xff0c;如果将分支条件的比较放到译码级来进行&#xff0c;则这部分只涉及取值级和译码级流水&#xff1b;另一个是Link操作&#xff0c;简单来说就是写寄存器&#xff0c;这部则主要…...

Java 多线程编程:提升系统并发处理能力!

多线程是 Java 中实现并发任务执行的关键技术&#xff0c;能够显著提升程序在多核处理器上的性能以及处理多任务的能力。本文面向初级到中级开发者&#xff0c;从多线程的基本定义开始&#xff0c;逐步讲解线程创建、状态管理、同步机制、并发工具以及新兴的虚拟线程技术。每部…...

Mininet 的详细设计逻辑

Mininet 是一个轻量级网络仿真工具&#xff0c;其核心目标是在单台物理机上快速构建复杂的虚拟网络拓扑&#xff0c;支持 SDN&#xff08;软件定义网络&#xff09;和传统网络协议的实验与验证。其设计逻辑围绕 虚拟化、模块化 和 灵活性 展开&#xff0c;以下是其详细设计架构…...

原生微信小程序实现导航漫游(Tour)

效果&#xff1a; 小程序实现导航漫游 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 定位&#xff1a;基础框架&#xff0c;提供 IoC&#xff08;控制反转&#xff09; 和 DI&#xff08;依赖注入&#xff09; 核心功能&#xff0c;管理对象生命周期及依赖关系。功能&#xff1a;支持事务管…...

神聖的綫性代數速成例題2. 行列式的性質

性質 1&#xff1a;行列式與它的轉置行列式相等&#xff1a; 設為行列式&#xff0c;為其轉置行列式&#xff0c;則。 性質 2&#xff1a;交換行列式的兩行 (列)&#xff0c;行列式變號&#xff1a; 若行列式經過交換第行和第行得到行列式&#xff0c;則。 性質 3&#xff…...

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训练&#xff0c;包括lora和grpo训练。我参考官方方法&#xff0c;使用模型Qwen2.5-3B-Instruct和数据集gsm8k&#xff0c;写了一个grpo训练的例子。 代码 这个代码加载模型Qwen2.5-3B-Instruct和数据集gsm8k。训练完成后先保存lora模型然后…...

【c++】【智能指针】shared_ptr底层实现

【c】【智能指针】shared_ptr底层实现 智能指针之前已经写过了&#xff0c;但是考虑到不够深入&#xff0c;应该再分篇写写。 1 shared_ptr 1.1 shared_ptr 是什么 std::shared_ptr是一个类模板&#xff0c;它的对象行为像指针&#xff0c;但是它还能记录有多少个对象共享它…...

python拉取大视频导入deepseek大模型解决方案

使用Python拉取大视频并导入大模型&#xff0c;需要综合考虑数据获取、存储、处理和资源管理&#xff0c;确保高效稳定地处理大视频数据&#xff0c;同时充分利用大模型的性能&#xff0c;以下是分步方案及代码示例&#xff1a; --- 1. 分块下载大视频&#xff08;避免内存溢出…...

【Python】面向对象

编程的两大特点 面向过程&#xff1a;着重于做什么面向对象&#xff08; oop&#xff09;&#xff1a;着重于谁去做 python是面向对象语言&#xff0c;面向对象三大特点&#xff1a;封装、继承、多态 面向对象&#xff1a;便于代码管理&#xff0c;方便迭代更新。 新式类、经…...

leetcode日记(100)填充每个节点的下一个右侧节点指针

和层序遍历差不多的思路&#xff0c;将节点储存在队列里&#xff0c;一边取出节点一边放入取出节点的左右节点&#xff0c;直到队列空。 /* // 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 是一个用于开发、交付和运行应用程序的开源平台&#xff0c;它可以让开发者将应用程序及其依赖打包到一个容器中&#xff0c;然后在任何环境中运行这个容器&#xff0…...

python语法

1. 前面先写import导入模块&#xff0c;完整的语法是&#xff1a; [from 模块名] import [模块 | 类 | 变量 | 函数 | *] [as 别名] 语法还可以是&#xff1a; from 模块名 import 功能名 如果import整个模块的话&#xff0c;需要用.功能名()&#xff0c;来用这个功能&#xff…...

Dify使用部署与应用实践

最近在研究AI Agent&#xff0c;发现大家都在用Dify&#xff0c;但Dify部署起来总是面临各种问题&#xff0c;而且我在部署和应用测试过程中也都遇到了&#xff0c;因此记录如下&#xff0c;供大家参考。Dify总体来说比较灵活&#xff0c;扩展性比较强&#xff0c;适合基于它做…...

微信小程序接入DeepSeek模型(火山方舟),并在视图中流式输出

引言&#xff1a; DeepSeek&#xff0c;作为一款先进的自然语言处理模型&#xff0c;以其强大的文本理解和生成能力著称。它能够处理复杂的文本信息&#xff0c;进行深度推理&#xff0c;并快速给出准确的回应。DeepSeek模型支持流式处理&#xff0c;这意味着它可以边计算边输…...

前端性能优化指标及优化方案

前端性能优化的核心目标是 提高页面加载速度、降低交互延迟、减少资源占用。常见的 Web 性能指标包括 LCP、FID、CLS、TTFB、TTI、FCP 等。 关键性能指标&#xff08;Web Vitals&#xff09; 指标优化方案 &#xff08;1&#xff09;LCP&#xff08;Largest Contentful Paint&…...