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

LeetCode 33. 搜索旋转排序数组:二分查找的边界艺术

文章目录

    • 问题描述
    • 解决思路
    • 代码实现
    • 关键点解析
      • 1. 为什么用 `nums[left] <= nums[mid]`?
      • 2. 示例分析
        • 案例 1:数组 `[3, 1]`,目标值 `1`
        • 案例 2:数组 `[5]`,目标值 `5`
    • 边界条件处理
      • 1. 单元素数组
      • 2. 完全有序数组
      • 3. 严格递增与重复值
    • 常见疑问
      • Q:为什么不能使用 `nums[left] < nums[mid]`?
    • 总结

问题描述

在旋转后的有序数组中搜索目标值。假设数组原本按升序排列,但在某个未知下标处进行了旋转(例如 [0,1,2,4,5,6,7] 旋转后可能变为 [4,5,6,7,0,1,2])。要求时间复杂度为 O(log n)

示例:

输入:nums = [4,5,6,7,0,1,2], target = 0  
输出:4  
解释:目标值 0 位于旋转后的右半部分。

解决思路

旋转后的数组可视为两个有序子数组的组合。利用 二分查找 的关键在于判断哪一部分是有序的,并检查目标值是否在该范围内。核心步骤如下:

  1. 判断有序区间:通过比较 nums[left]nums[mid],确定左半或右半是否有序。
  2. 缩小搜索范围:根据目标值是否在有序区间内,调整左右指针。

代码实现

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid; // 直接命中// 判断左半部分是否有序if (nums[left] <= nums[mid]) { // 目标值在左半有序区间内if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else { // 右半部分有序// 目标值在右半有序区间内if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}

关键点解析

1. 为什么用 nums[left] <= nums[mid]

  • 判断有序区间
    nums[left] <= nums[mid],说明左半部分 [left, mid] 是有序的(未包含旋转点)。否则右半部分有序。
  • 边界处理
    left == mid 时(例如数组长度为 1),nums[left] == nums[mid],等号确保这种情况被正确归类为“左半有序”。

2. 示例分析

案例 1:数组 [3, 1],目标值 1
  • left = 0, mid = 0,满足 nums[left] <= nums[mid](3 ≤ 3)。
  • 目标值不在左半部分(1 < 3 不成立),调整 left = mid + 1,最终找到目标值。
案例 2:数组 [5],目标值 5
  • 若去掉等号,条件 nums[left] < nums[mid] 不成立,程序误判右半有序。
  • 检查右半部分时,target > nums[mid] 不成立,错误调整 right = mid - 1,导致返回 -1

边界条件处理

1. 单元素数组

nums.length == 1 时,left == mid == right,必须通过等号确保逻辑正确。

2. 完全有序数组

若数组未旋转(例如 [1,2,3,4,5]),逻辑仍能正确判断左半有序。

3. 严格递增与重复值

题目假设元素唯一,无需处理重复值。若存在重复值需调整条件(如 nums[left] < nums[mid])。


常见疑问

Q:为什么不能使用 nums[left] < nums[mid]

  • 边界问题:当 left == mid 时,条件不成立,导致误判右半有序。
  • 错误示例
    数组 [5],目标值 5。若用 <,程序错误调整 right = mid - 1,最终返回 -1

总结

  1. 核心逻辑:通过 nums[left] <= nums[mid] 判断有序区间,结合目标值范围调整指针。
  2. 边界条件:等号处理 left == mid 的临界情况,确保单元素区间被正确识别。
  3. 时间复杂度:O(log n),每次循环将搜索范围减半。

关键启示:二分查找的难点不仅在于算法框架,更在于对边界条件的精准处理。理解每一行代码背后的意图,才能避免“差之毫厘,谬以千里”。

相关文章:

LeetCode 33. 搜索旋转排序数组:二分查找的边界艺术

文章目录 问题描述解决思路代码实现关键点解析1. 为什么用 nums[left] < nums[mid]&#xff1f;2. 示例分析案例 1&#xff1a;数组 [3, 1]&#xff0c;目标值 1案例 2&#xff1a;数组 [5]&#xff0c;目标值 5 边界条件处理1. 单元素数组2. 完全有序数组3. 严格递增与重复…...

Rust 学习笔记:关于 HashMap 的练习题

Rust 学习笔记&#xff1a;关于 HashMap 的练习题 Rust 学习笔记&#xff1a;关于 HashMap 的练习题以下代码能否通过编译&#xff1f;若能&#xff0c;输出是&#xff1f;以下代码能否通过编译&#xff1f;若能&#xff0c;输出是&#xff1f; Rust 学习笔记&#xff1a;关于 …...

(头歌作业)—6.1 葡萄酒评论分析报告(project)

第1关&#xff1a;葡萄酒评论分析报告——国家列表和平均分 任务描述 本关任务&#xff1a;编写程序&#xff0c;多维度分析葡萄酒数据。 相关知识 葡萄酒评论分析报告描述 winemag-data.csv 文件 winemag-data.csv 包含 编号、国家、描述、评分、价格、省份 等 6列 和12974…...

下集:一条打包到底的静态部署之路

说完坑&#xff0c;再来讲正经操作。 这次我决定写得明明白白&#xff0c;清清楚楚&#xff0c;把那条“Spring Boot 扛着 Next.js 上线”的路子掰碎了揉细了告诉你。 无废话、无迷信、无AI幻觉。 第一步&#xff1a;Next.js 静态导出 项目根目录下的 next.config.js 要写得…...

多商户商城系统源码解析:开发直播电商APP的技术底层实战详解

随着直播电商的火爆&#xff0c;越来越多的创业者和企业都在寻求打造自己的多商户商城系统&#xff0c;以实现“人、货、场”三者的深度融合。然而&#xff0c;从一个简单的电商平台到一个功能完善的直播电商APP&#xff0c;其技术底层架构和实现过程并非一蹴而就。本文将从架构…...

每日Prompt:生成自拍照

提示词 帮我生成一张图片&#xff1a;图片风格为「人像摄影」&#xff0c;请你画一张及其平凡无奇的iPhone对镜自拍照&#xff0c;主角是穿着JK风格cos服的可爱女孩&#xff0c;在自己精心布置的可按风格的房间内的落地镜前用后置摄像头随手一拍的快照。照片开启了闪光灯&…...

LeetCode 热题 100_寻找重复数(100_287_中等_C++)(技巧)(暴力解法;哈希集合;二分查找)

LeetCode 热题 100_寻找重复数&#xff08;100_287_中等_C&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;暴力解法&#xff09;&#xff1a;思路二&#xff08;哈希集合&#xff09;&#xff1a;思路三&am…...

多模态学习(三)—— ROPE位置编码:从理论到实践

ROPE位置编码&#xff1a;从理论到LLaMA的实践 一、前言 ROPE&#xff08;Rotary Positional Embedding&#xff0c;旋转位置编码&#xff09;是一种通过旋转矩阵将位置信息融入Token Embedding的编码方法。相比传统Transformer的绝对位置编码&#xff0c;ROPE能更灵活地建模…...

Redis——过期删除策略和内存

过期删除策略 Redis可以对key设置过期时间&#xff0c;因此需要有相应的机制将已过期的键值对删除 设置了过期时间的key会存放在过期字典中&#xff0c;可以用presist命令取消key过期时间 过期字典存储在redisDb结构中&#xff1a; typedef struct redisDb {dict *dict; …...

Selenium无法定位元素的几种解决方案详解

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、frame/iframe表单嵌套 WebDriver只能在一个页面上对元素识别与定位&#xff0c;对于frame/iframe表单内嵌的页面元素无法直接定位。 解决方法&#xff1a; …...

开源项目实战学习之YOLO11:12.3 ultralytics-models-sam-encoders.py源码分析

👉 点击关注不迷路 👉 点击关注不迷路 👉 另外,前些天发现了一个巨牛的AI人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。感兴趣的可以点击相关跳转链接。 点击跳转到网站。 ultralytics-models-sam 1.sam-modules-encoders.pyblocks.py: 定义模型中的各…...

Bitmap原理及Hive去重方式对比

1. 什么是 Bitmap&#xff1f; Bitmap&#xff08;位图&#xff09;是一种用位&#xff08;bit&#xff09;来表示数据集合的数据结构。每个位代表一个元素是否存在&#xff0c;比如&#xff1a; 一个长度为N的bitmap&#xff0c;每一位对应一个元素的状态&#xff08;0或1&a…...

力扣-比特位计数(统计一个数二进制下1的个数)

下面是题面 1.用c的内置函数__builtin_popcount&#xff08;&#xff09; 语法&#xff1a;__builtin_popcount&#xff08;int x&#xff09;&#xff0c;函数会返回一个二进制下x所含的1的个数 2.直接数位枚举 这是最慢也是暴力做法&#xff0c;写法也很简单 用一个while循环…...

开源项目实战学习之YOLO11:12.2 ultralytics-models-sam-decoders.py源码分析

👉 点击关注不迷路 👉 点击关注不迷路 👉 另外,前些天发现了一个巨牛的AI人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。感兴趣的可以点击相关跳转链接。 点击跳转到网站。 ultralytics-models-sam 1.sam-modules-decoders.pyblocks.py: 定义模型中的各…...

Python训练营打卡Day28

浙大疏锦行 DAY 28 类的定义和方法 知识点回顾&#xff1a; 1.类的定义 2.pass占位语句 3.类的初始化方法 4.类的普通方法 5.类的继承&#xff1a;属性的继承、方法的继承 作业 题目1&#xff1a;定义圆&#xff08;Circle&#xff09;类 要求&#xff1a; 1.包含属性&#x…...

【前端基础】HTML元素隐藏的四个方法(display设置为none、visibikity设置为hidden、rgba设置颜色、opacity设置透明度)

HTML元素隐藏的四个方法 1、display设置为none 元素不显示出来。不占位置&#xff0c;也没有任何空间。就不存在一样。 2、visibility设置为hidden 默认&#xff1a;visible。元素可见设置为hidden&#xff1a;元素不可见&#xff0c;但是会占据这个元素应该占用的空间。 3、…...

STM32中的DMA

DMA介绍 什么是DMA? DMA&#xff08;Direct Memory Access&#xff0c;直接存储器访问&#xff09;提供在外设与内存、存储器和存储器之间的高速数据传输使用。它允许不同速度的硬件装置来沟通&#xff0c;而不需要依赖于CPU&#xff0c;在这个时间中&#xff0c;CPU对于内存…...

小型气象站应用之鱼塘养殖方案

概述 "看天吃饭"&#xff0c;在农村经常听到这句话&#xff0c;鱼塘也不例外。天气的急剧变化&#xff0c;或连续的不利天气都有可能造成鱼类"浮头"&#xff0c;甚至"翻肚子"&#xff0c;更甚至"翻塘"&#xff0c;一年白忙活了。 鱼塘…...

Makefile变量冲突与包含关系解析

Nuttx makefile每层独立&#xff0c;除非显示的通过include的方式包含。 Makefile调试技巧 打印变量 $(info CSRCS$(CSRCS))查看变量赋值过程 make --debugv在 Makefile 中&#xff0c;变量的作用域和可见性取决于 包含关系&#xff08;include&#xff09; 和 递归调用&…...

2025/517学习

对离群值怎么操作。这个就是拟合操作的。用更弯曲的曲线去拟合&#xff0c;如常见函数log 多元回归和单元回归 如题&#xff0c;如果我有多个自变量&#xff0c;来对一个因变量进行OLS回归&#xff0c;有没有operator可以做到&#xff1f;(ts_regression似乎只支持一个…...

浅谈前端架构设计与工程化

引言 在当今快速发展的Web开发领域&#xff0c;前端已经从简单的页面展示演变为复杂的应用程序开发。随着项目规模的扩大和团队协作的需求增加&#xff0c;良好的前端架构设计和工程化实践变得至关重要。本文将探讨如何构建可维护、可扩展的前端架构&#xff0c;并介绍现代前端…...

JMeter 教程:编写 POST 请求脚本访问百度

目录 ✅ 教程目的 &#x1f6e0;️ 环境要求 &#x1f4c4; 实操步骤 第一步&#xff1a;启动 JMeter 第二步&#xff1a;添加测试计划和线程组 1.右键左侧 Test Plan&#xff08;测试计划&#xff09; 2.选择 Add → Threads (Users) → Thread Group&#xff08;线程组…...

Typescript学习教程,从入门到精通,TypeScript 函数语法知识点及案例代码(5)

TypeScript 函数语法知识点及案例代码 TypeScript 提供了丰富的函数语法特性&#xff0c;使得函数定义更加灵活和强大。以下将详细介绍 TypeScript 中函数的相关语法&#xff0c;包括函数定义、可选参数、默认参数、剩余参数、重载函数、递归函数、匿名函数、箭头函数以及回调…...

【51单片机定时器/计数器】

目录 简介 定时器配置流程 1.配置定时器工作方式寄存器TMOD 2.配置中断寄存器TCON 3.定时时间计算公式 4.配置中断允许寄存器IE 5.使用中断函数完成中断 简介 定时器/计数器本质都是对脉冲信号进行计数&#xff0c;区别在于作为定时器时的脉冲信号来自于晶振12分频&…...

Oracle 的 ASSM 表空间

Oracle 的 ASSM&#xff08;Automatic Segment Space Management&#xff09;表空间 是一种自动管理段空间的技术&#xff0c;通过位图&#xff08;Bitmap&#xff09;机制跟踪数据块的使用情况&#xff0c;替代传统的手动管理&#xff08;MSSM&#xff0c;即 Freelist 管理&am…...

C++学习:六个月从基础到就业——C++11/14:auto类型推导

C学习&#xff1a;六个月从基础到就业——C11/14&#xff1a;auto类型推导 本文是我C学习之旅系列的第四十一篇技术文章&#xff0c;也是第三阶段"现代C特性"的第三篇&#xff0c;主要介绍C11/14中的auto类型推导机制。查看完整系列目录了解更多内容。 引言 在现代C…...

select语句的书写顺序

一.MySQL SELECT语句的执行顺序 MySQL中SELECT语句的执行顺序与SQL语句的书写顺序不同&#xff0c;理解这个执行顺序对于编写高效查询非常重要。 1.标准SELECT语句的执行顺序 FROM子句&#xff08;包括JOIN操作&#xff09; 首先确定数据来源表执行表连接操作 WHERE子句 对F…...

OpenWebUI新突破,MCPO框架解锁MCP工具新玩法

大家好&#xff0c;Open WebUI 迎来重要更新&#xff0c;现已正式支持 MCP 工具服务器&#xff0c;但 MCP 工具服务器需由兼容 OpenAPI 的代理作为前端。mcpo 是一款实用代理&#xff0c;经测试&#xff0c;它能让开发者使用 MCP 服务器命令和标准 OpenAPI 服务器工具&#xff…...

【Day28】

总结&#xff1a; Python 通过缩进来定义代码块的结构。当解释器遇到像 def, class, if, for 这样的语句&#xff0c;并且后面跟着冒号 : 时&#xff0c;它就期望接下来会有一个或多个缩进的语句来构成这个代码块。如果它没有找到任何缩进的语句&#xff08;即代码块是空的&am…...

STM32 | FreeRTOS 消息队列

01 一、概述 队列又称消息队列&#xff0c;是一种常用于任务间通信的数据结构&#xff0c;队列可以在任务与任务间、中断和任务间传递信息&#xff0c;实现了任务接收来自其他任务或中断的不固定长度的消息&#xff0c;任务能够从队列里面读取消息&#xff0c;当队列中的消…...

Vue-事件修饰符

事件修饰符 prevent &#xff08;阻止默认事件&#xff09; 超链接 点击事件 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>事件修饰符</title><!-- 引入Vue --><script …...

c++函数调用运算符及类型转换运算符重载

author: hjjdebug date: 2025年 05月 17日 星期六 14:44:48 CST descrip: c函数调用运算符及类型转换运算符重载 文章目录 0. 前言. 运算符包括以下运算符.1. 运算符重载语句一般格式:2. 函数调用运算符&#xff1a;3. 类型转换运算符&#xff1a; 例如 int(); double(); bool(…...

如何在 Windows 10 或 11 中安装 PowerShellGet 模块?

PowerShell 是微软在其 Windows 操作系统上提供的强大脚本语言,可用于通过命令行界面自动化各种任务,适用于 Windows 桌面或服务器环境。而 PowerShellGet 是 PowerShell 中的一个模块,提供了用于从各种来源发现、安装、更新和发布模块的 cmdlet。 本文将介绍如何在 PowerS…...

84.评论日记

原链接 这个视频我发了四五条评论。评论内容甚至和下面这个视频内的其他评论一样。 找了另外的账号也发了。 发现&#xff0c;无论是我这个账号&#xff0c;还是其他的账号&#xff0c;评论都无法看到。 我大胆猜测有一种机制&#xff0c;某些官号会被设置成一种高检测的等…...

一周学会Pandas2 Python数据处理与分析-Pandas2数据添加修改删除操作

锋哥原创的Pandas2 Python数据处理与分析 视频教程&#xff1a; 2025版 Pandas2 Python数据处理与分析 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 对数据的修改、增加和删除在数据整理过程中时常发生。修改的情况一般是修改错误&#xff0c;还有一种情况是格式转换…...

荷兰国旗问题 之 指针划分区间问题

文章目录 首先介绍一下什么是荷兰国旗问题&#xff1f;问题描述为&#xff1a;给定一个由红色、白色和蓝色三种颜色组成的无序数组&#xff0c;将数组元素按颜色排序&#xff0c;使得所有红色元素在前&#xff0c;白色元素居中&#xff0c;蓝色元素在后。这里的 “颜色” 通常用…...

冒泡排序-java

public class BubbleSort{ public static void bubbleSort(int[] arr) { int n arr.length; boolean swapped; // 外层循环控制遍历的轮数 for (int i 0; i < n - 1; i) { swapped false; for (int j 0; …...

进阶-数据结构部分:​​​​​​​2、常用排序算法

飞书文档https://x509p6c8to.feishu.cn/wiki/FfpIwIPtviMMb4kAn3Sc40ABnUh 常用排序算法 这几种算法都是常见的排序算法&#xff0c;它们的优劣和适用场景如下&#xff1a; 冒泡排序&#xff08;Bubble Sort&#xff09;&#xff1a;简单易懂&#xff0c;时间复杂度较高&…...

人工智能-自然语言与语音产品实现

一、语义相似度 &#xff08;一&#xff09;、文本向量化 1、文本向量化&#xff08;Text Vectorization&#xff09; 是自然语言处理&#xff08;NLP&#xff09;中的核心预处理步骤&#xff0c;旨在将人类语言的文本转换为计算机可处理的数值向量&#xff08;数学表达&…...

阿里巴巴开源移动端多模态LLM工具——MNN

MNN 是一个高效且轻量级的深度学习框架。它支持深度学习模型的推理和训练&#xff0c;并在设备端的推理和训练方面具有行业领先的性能。目前&#xff0c;MNN 已集成到阿里巴巴集团的 30 多个应用中&#xff0c;如淘宝、天猫、优酷、钉钉、闲鱼等&#xff0c;覆盖了直播、短视频…...

SpringBootAdmin:全方位监控与管理SpringBoot应用

监控的意义 1. 监控服务状态是否宕机 2. 监控服务运行指标 (内存,虚拟机,线程,请求等) 3. 监控日志 4. 管理服务 (服务下线) 可视化监控平台 Spring Boot Admin, 开源社区项目, 用于管理和监控SpringBoot应用程序. 客户端注册到服务端, 通过HTTP请求方式, 服务端定期从客…...

SAP HCM 0008数据存储逻辑

0008信息类型&#xff1a;0008信息类型是存储员工基本薪酬的地方&#xff0c;因为很多企业都会都薪酬带宽&#xff0c;都会按岗定薪&#xff0c;所以在上线前为体现工资体系的标准化&#xff0c;都会在配置对应的薪酬关系&#xff0c;HCM叫间接评估&#xff0c;今天我们就分析下…...

【springcloud学习(dalston.sr1)】Config配置中心-ConfigServer端与Git通信(含源代码)(十三)

该系列项目整体介绍及源代码请参照前面写的一篇文章【springcloud学习(dalston.sr1)】项目整体介绍&#xff08;含源代码&#xff09;&#xff08;一&#xff09; springcloud学习&#xff08;dalston.sr1&#xff09;系统文章汇总如下&#xff1a; 【springcloud学习(dalston…...

2020CCPC河南省赛题解

A. 班委竞选 签到题&#xff0c;模拟。 #include <bits/stdc.h> #define x first #define y second #define int long long //#define double long doubleusing namespace std; typedef unsigned long long ULL ; typedef pair<int,int> PII ; typedef pair<d…...

C语言输入函数对比解析

目录 C语言输入函数全家福&#xff08;和它们的秘密&#xff09;fgetsgetsscanfgetcharfscanf函数对比表灵魂总结 哈哈&#xff0c;看来你正在和C语言的输入函数们玩“大家来找茬”&#xff01;放心&#xff0c;我会用最接地气的方式给你讲明白&#xff0c;保证比看《甄嬛传》还…...

python四则运算计算器

python四则运算计算器 是谁说&#xff0c;python不好写计算器的&#xff0c;我亲自写个无ui的计算器功能&#xff0c;证明这是谣言 step1:C:\Users\wangrusheng\Downloads\num.txt 15 - 4 * 3 10 / 2(5 3) * 2 6 / 31/2 * 8 3/4 * 4 - 0.52.5 * (4 1.6) - 9 / 3-6 12 * (…...

BUUCTF——Nmap

BUUCTF——Nmap 进入靶场 类似于一个nmap的网站 尝试一下功能 没什么用 看看数据包 既然跟IP相关 伪造一个XXF看看 拼接了一下没什么用 果然没这么简单 尝试一下命令注入 构造payload 127.0.0.1 | ls 应该有过滤 加了个\ 直接构造个php木马上传试试 127.0.0.1 | <?…...

【Changer解码头详解及融入neck层数据的实验设计】

Changer解码头详解 ChangerEx中的 Changer 解码头&#xff08;定义在 [changer.py](file://opencd\models\decode_heads\changer.py)&#xff09;是基于双时相输入的&#xff0c;用于遥感变化检测任务。下面我将详细解释&#xff1a; &#x1f3af; 一、解码头输入数据来源 输…...

深度学习推理引擎---OpenVINO

OpenVINO&#xff08;Open Visual Inference & Neural Network Optimization Toolkit&#xff09;是英特尔开发的开源工具套件&#xff0c;旨在优化和加速深度学习模型在英特尔硬件&#xff08;CPU、GPU、VPU、FPGA等&#xff09;上的推理性能&#xff0c;同时支持从训练到…...

JavaScript splice() 方法

1. JavaScript splice() 方法 1.1. 定义和用法 splice() 方法用于添加或删除数组中的元素。   注意&#xff1a;这种方法会改变原始数组。   返回值&#xff1a;如果删除一个元素&#xff0c;则返回一个元素的数组。 如果未删除任何元素&#xff0c;则返回空数组。 1.2. …...