LeetCode 153:找旋转排序数组中的最小值(二分查找) —— 题解
欢迎阅读 欢迎来到「寻找旋转排序数组中的最小值」题解之旅本文将带你从在旋转过的有序序列中找最小元素这一直观场景出发深入理解二段性二分的巧妙运用并掌握如何与右端点比较判断所在段来在 O(log n) 内定位最小值。在开始之前建议你先了解题目背景这是 LeetCode 153 题给定无重复的旋转排序数组nums原升序数组在某点旋转返回最小元素。本质上数组由两段递增拼接而成最小值是两段的分界点问题转化为二分找到二段性的边界。明确学习目标掌握与右端点比较的二分模板理解为什么不能用左端点比较并熟练处理未旋转与单元素等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [3,4,5,1,2]输出1nums [4,5,6,7,0,1,2]输出0。本文将从问题转化、右端点判据、区间收缩、返回结果到代码实现层层递进。即使你对二段性二分还不熟悉我们也会从比右端点大的在左边那段比它小的在右边那段这一直觉出发让你轻松抓住核心思想——与右端比大小分界点即最小值。现在让我们一起二分定位找出旋转数组的最小值吧 一.题目153. 寻找旋转排序数组中的最小值 - 力扣LeetCode​二.做题思路一、问题分析前置分析题目要求在旋转排序数组无重复由升序数组旋转得到中返回最小元素。关键约束数组无重复元素由两段递增组成最小值是两段的分界点。核心思路取右端点 x nums[n-1]为基准数组可分为两段——第一段元素都 x第二段元素都 x含最小值二分找分界点。二、算法策略右端点基准二分核心步骤初始化left 0、right n - 1取基准x nums[right]。二分收敛while (left right)mid下取整left (right - left) / 2。段判断nums[mid] x→ mid 在第一段较大段最小值在右半left mid 1nums[mid] x→ mid 在第二段较小段含最小值right mid。返回循环结束后nums[left]即最小值。示例执行过程nums [3,4,5,1,2]x nums[4] 2阶段leftrightmidnums[mid] vs x操作结果①0425 2第一段收缩左侧left3②3431 ≤ 2第二段收缩右侧right3收敛33——返回 nums[3]11三、正确性说明简单版本二段性成立无重复时旋转数组所有元素中大于右端点的都在第一段旋转前的左侧大数小于右端点的都在第二段旋转后的最小值及其右侧判据nums[mid] x恰好区分两段不会误判。最小值必在第二段最小值 ≤ 右端点除非数组未旋转此时最小值是首元素同样 ≤ x所以nums[mid] x时保留 mid 向左收敛不会漏掉最小值。收缩方向正确第一段丢弃左半第二段保留 mid区间单调收敛到第二段起点即最小值不漏解。终止性left mid 1与right mid下取整保证mid right均严格缩小不会死循环。四、实现细节边界防护初始化left 0、right n - 1、x nums[right]。边界防护n 1时循环不进入返回nums[0]未旋转数组完全升序时所有元素 ≤ x二分会收敛到left 0返回最小值无重复保证nums[mid] x不会出现除 mid right 时但 mid right 恒成立。复杂度时间 O(log n)每次排除一半空间 O(1)仅常数个变量。关键判断if (nums[mid] x) left mid 1; else right mid;段判断收敛、while (left right)循环边界。五、返回值目标映射返回nums[left]最小元素本身对应题目返回数组中的最小元素。三.代码class Solution { public: int findMin(vectorint nums) { int left 0; // 区间左端点 int n nums.size(); int right n - 1; // 区间右端点 int x nums[right]; // 基准右端点值用于划分两段 // 1. 二段性二分与右端点比较判断 mid 在较大段还是较小段 while (left right) { int mid left (right - left) / 2; // mid 下取整配合 right mid if (nums[mid] x) { left mid 1; // 较大段最小值在右半丢弃左半含 mid } else { right mid; // 较小段含最小值保留 mid 向左收敛 } } // 2. 收敛点即最小值所在位置 return nums[left]; } };四、易错点分析难点1为什么基准必须选右端点而非左端点int x nums[right]; // 右端点 if (nums[mid] x) // 判据选右端点作基准时旋转数组天然形成大于 x 的一段 小于 x 的一段的二段性无重复。若选左端点当数组未旋转完全升序时所有元素都 ≥ 左端点判据nums[mid] nums[left]恒为真二分只会一路向右收缩最终错误收敛到末尾最大值。右端点基准则天然覆盖未旋转情形此时最小值就是首元素二分会收敛到 left0。难点2为什么nums[mid] x时可以直接保留 midelse { right mid; // nums[mid] xmid 可能在最小值或其右侧 }由于无重复nums[mid] x说明 mid 在第二段最小值右侧或恰为最小值nums[mid] x只在 mid right 时成立而mid right恒成立故实际只会出现。最小值 ≤ x 恒成立所以保留 mid 向左收敛不会把最小值排除在区间外。难点3nums[mid] x时为什么可以安全丢弃左半if (nums[mid] x) left mid 1;nums[mid] x说明 mid 在第一段旋转点之前的升序大数段。第一段的最小值即首元素也大于 x而真正的全局最小值在第二段所以整个左半含 mid都不可能含最小值可安全丢弃——这正是二段性带来的确定性排除。难点4未旋转数组的隐式处理无需特判// nums [11,13,15,17]x 17 // 所有 nums[mid] x二分一路 right mid收敛到 left 0未旋转时数组完全升序最小值就是nums[0]。由于所有元素 ≤ x判据永远走else分支区间持续向左收敛到 0返回首元素即最小值。若误加先判断是否旋转的特判不仅多余还可能因边界访问引入 bug。五、流程图 闭幕 恭喜你完成了「寻找旋转排序数组中的最小值」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题利用旋转数组的二段性最小值左侧所有元素都大于右侧所有元素通过将nums[mid]与右端点值x nums[right]比较来判断mid在哪一段。为什么选择右端点作为基准而不是左端点如果用左端点做比较会遇到什么问题当nums[mid] x时执行left mid 1否则执行right mid。为什么当nums[mid] x时最小值一定在mid左侧含mid请从数组两段的数值大小关系解释。如果数组未旋转即升序数组代码是否仍然正确收敛点会是哪个位置请验证。本题要求返回最小值数值如果要求返回最小值的下标代码只需改动哪一处延伸挑战如果题目改为寻找旋转排序数组中的最大值你能否仅修改比较基准和收缩方向来实现请描述具体改动。如果数组包含重复元素例如[2,2,2,0,2]当前的nums[mid] x判断逻辑还正确吗应如何改进如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案选择右端点作为基准是因为旋转数组的右端点位于较小段最小值所在段与mid比较能清晰判断mid在较大段还是较小段若用左端点当mid处于较小段时nums[mid] nums[left]也能判断但需要额外处理未旋转的情况且代码分支会变复杂。当nums[mid] x时说明mid位于较小段因为较小段的所有值都 ≤ x而最小值就在mid的左侧含mid因此right mid向左收敛不会丢失最小值。未旋转时正确数组升序右端点x为最大值nums[mid] x恒为假因此right不断左移最终left收敛到 0返回nums[0]为最小值正确。若返回下标只需将return nums[left]改为return left。延伸挑战答案挑战1找最大值可将基准改为左端点比较nums[mid]与nums[left]若nums[mid] nums[left]最大值在右半left mid否则最大值在左半right mid - 1注意上取整避免死循环。挑战2重复元素会破坏二段性如[2,2,2,0,2]nums[mid] x无法判断方向需将right--来逐步消除重复退化为 O(n) 的最坏情况但平均仍较快。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨

相关新闻

蓝桥杯单片机国赛备考:从模块化设计到实时系统架构的工程实践

蓝桥杯单片机国赛备考:从模块化设计到实时系统架构的工程实践

1. 从“真题”到“实战”:第五届国赛的独特价值与备考定位 如果你正在准备蓝桥杯单片机国赛,手头肯定不缺历年真题。但第五届国赛的真题,在我看来,是承前启后的一个关键节点。它不像早期几届那样,还在摸索题型和难度&a…

2026/11/20 16:36:57 阅读更多 →
PLC编程框架实战:状态机与模块化设计,轻松搞定变频器RS485通信

PLC编程框架实战:状态机与模块化设计,轻松搞定变频器RS485通信

最开始接触 PLC 编程的时候,很多朋友的习惯是:拿到项目直接打开编程软件,一边看着 IO 表一边拖梯形图,常开常闭触点、线圈、定时器随手往上放。程序少的时候还好说,等到设备动作越来越多,程序越来越长&…

2026/11/20 16:36:57 阅读更多 →
embOS-MPU:RTOS内存保护单元实现任务级安全隔离实践

embOS-MPU:RTOS内存保护单元实现任务级安全隔离实践

1. 为什么嵌入式系统突然需要“安全”了做嵌入式开发十来年,早年我们聊“嵌入式安全”,大家第一反应就是给设备加把锁、把固件加密、防抄板。但随着物联网设备大规模铺开,事情早就变了。现在终端设备面临的威胁不是“能不能被拆开读写Flash”…

2026/11/16 0:27:48 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻