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) 的最坏情况但平均仍较快。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨