二分查找求旋转排序数组最小值：153 题解深度拆解与 154 重复元素进阶-北京尧图网络

二分查找求旋转排序数组最小值153 题解深度拆解与 154 重复元素进阶【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 仓库中的 153. 寻找旋转排序数组中的最小值题解文档系统讲解在旋转后的升序数组中二分查找最小值这一经典题型从解空间定义、左右有序部分的判定逻辑到不套用传统二分模板的简洁写法并延伸至仓库中 91/binary-search.md 提供的另一种比较 nums[0]的解法以及 154. 寻找旋转排序数组中的最小值 II 处理重复元素的进阶版本。读完本文你将掌握旋转数组最值类二分问题的核心判别条件与防死循环细节并能随手写出 bug-free 的代码。题目背景什么是旋转排序数组已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]旋转 4 次可得到[4,5,6,7,0,1,2]旋转 7 次即不旋转仍为[0,1,2,4,5,6,7]。旋转一次的定义数组[a[0], a[1], ..., a[n-1]]旋转一次的结果为[a[n-1], a[0], a[1], ..., a[n-2]]。本题153的输入约束为n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数互不相同这是与 154 题的关键区别nums 原本是升序排序数组并进行了 1 至 n 次旋转典型示例输入输出说明nums [3,4,5,1,2]1原数组[1,2,3,4,5]旋转 3 次nums [4,5,6,7,0,1,2]0原数组[0,1,2,4,5,6,7]旋转 4 次nums [11,13,15,17]11原数组旋转 4 次即完全有序未发生实际旋转思路利用部分有序进行二分这道题与仓库中 33. 搜索旋转排序数组同属一类数组不再整体有序但以旋转点为分界左右两部分各自有序。与 33 题找指定值不同本题目标是找最小值因此可以不照搬二分讲义中的传统模板而采用一种更简洁的写法。解空间定义解空间为(l, r)整体模板为while l r: # your code here return nums[l] # or nums[r]核心判别mid 在左半有序部分还是右半有序部分与普通旋转数组找指定值类似先判断 mid 落在哪一部分如果 mid 在左侧有序部分说明最小值一定在 mid 右侧直接l mid 1否则mid 在右侧有序部分最小值可能是 mid 本身或在 mid 左侧令r mid这里有两个极易踩坑的细节原文档特别强调mid 是向下取整得到的mid (l r) // 2因此r mid不会导致死循环而如果写成l mid则可能死循环。这是收缩右边界用 mid、收缩左边界用 mid 1的根本原因。如果左端点的值小于右端点的值则可以提前退出。此时区间[l, r]已经整体有序旋转点在区间之外nums[l]必然就是最小值直接返回即可无需继续二分。关键点如果左端点的值小于右端点的值则当前区间整体有序可以提前返回nums[l]代码实现Python3class Solution: def findMin(self, nums: List[int]) - int: l, r 0, len(nums) - 1 while l r: # important if nums[l] nums[r]: return nums[l] mid (l r) // 2 # left part if nums[mid] nums[r]: l mid 1 else: # right part r mid # l or r is not important return nums[l]代码逐行解读l, r 0, len(nums) - 1左右指针指向闭区间两端while l r区间至少还有两个元素时继续收缩最终l与r收敛到同一个索引即最小值下标if nums[l] nums[r]: return nums[l]当前区间整体有序直接返回左端点mid (l r) // 2向下取整取中点if nums[mid] nums[r]mid 位于左侧有序部分因为左侧部分的元素都大于右侧部分的所有元素包括nums[r]最小值在右侧收缩左边界else: r midmid 位于右侧有序部分含中点本身收缩右边界但保留 mid。复杂度分析令 n 为数组长度时间复杂度O(log n)每轮循环将搜索区间折半空间复杂度O(1)仅使用常数个指针变量仓库佐证二分讲义的另一种解法本题解文档的前置知识指向仓库二分讲义 thinkings/binary-search-1.md二分专题上篇该讲义的核心观点是二分法的中心是折半根据什么条件舍弃哪一部分而 91/binary-search.md第一期讲义-二分法的寻找最值改进的二分一节专门收录了本题并给出了另一种与 nums[0] 比较的解法旋转点左侧元素都大于数组第一个元素旋转点右侧元素都小于数组第一个元素基于此建立nums[mid]与nums[0]的联系找到数组的中间元素 mid如果nums[mid] nums[0]说明 mid 在左侧有序部分最小值在右侧向左收缩如果nums[mid] nums[0]说明 mid 在右侧有序部分最小值在左侧向右收缩当nums[mid] nums[mid 1]mid1 是最小值或nums[mid - 1] nums[mid]mid 是最小值时找到旋转点停止搜索。对应代码Python位于 91/binary-search.mdclass Solution: def findMin(self, nums): # If the list has just one element then return that element. if len(nums) 1: return nums[0] # left pointer left 0 # right pointer right len(nums) - 1 # if the last element is greater than the first element then there is no rotation. # e.g. 1 2 3 4 5 7. Already sorted array. # Hence the smallest element is first element. A[0] if nums[right] nums[0]: return nums[0] # Binary search way while right left: # Find the mid element mid left (right - left) / 2 # if the mid element is greater than its next element then mid1 element is the smallest # This point would be the point of change. From higher to lower value. if nums[mid] nums[mid 1]: return nums[mid 1] # if the mid element is lesser than its previous element then mid element is the smallest if nums[mid - 1] nums[mid]: return nums[mid] # if the mid elements value is greater than the 0th element this means # the least value is still somewhere to the right as we are still dealing with elements greater than nums[0] if nums[mid] nums[0]: left mid 1 # if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left else: right mid - 1两种解法对比小结解法一与 nums[r] 比较代码更简洁配合nums[l] nums[r]提前退出是本文主文档的推荐写法解法二与 nums[0] 比较直接定位旋转点最小值即旋转点本身或其右邻元素思路直观但需要额外处理数组未旋转和长度为 1的边界情况。进阶154 题——存在重复元素怎么办仓库配套文档 154. 寻找旋转排序数组中的最小值 II 是本题的直接延伸nums中可能存在重复元素。同样要求找出最小元素约束1 n 5000-5000 nums[i] 5000。示例输入nums [1,3,5]输出 1输入nums [2,2,2,0,1]输出 0154 题解文档给出的思路在 153 基础上做了三处关键调整沿用 153 的核心左端点值小于右端点值则提前退出否则取中点判断其位于左半有序还是右半有序。无法判断 mid 归属时只能排除一个元素当nums[mid] nums[l]时无法确定 mid 在左半还是右半例如[2,2,2,2,0,1,2]中 mid 在左侧有序部分而[2,0,1,2,2,2]中 mid 在右侧有序部分。此时无法排除一半解只能退而求其次排除一个。这意味着最坏情况下算法无法达到O(log n)这是与无重复元素版本的本质区别。必须与右端点比较且相等时舍弃右端点判断左半还是右半需要用nums[mid]与nums[r]比较而不能与nums[l]比较与左端点比较无法保证任何情况下都能排除一半当nums[mid] nums[r]时执行r - 1舍弃右端点因为向下取整的中点在左端点一侧舍弃右端点不会错过最小值。对应代码Python3class Solution: def findMin(self, nums: List[int]) - int: l, r 0, len(nums) - 1 while l r: if nums[l] nums[r]: return nums[l] mid (l r) // 2 # [2,2,2,0,1] if nums[mid] nums[r]: l mid 1 elif nums[mid] nums[r]: r mid else: r - 1 return nums[l] # or nums[r]复杂度分析154 题时间复杂度O(n)最坏情况大量重复元素需要扫描整个数组空间复杂度O(1)总结从 153 到 154旋转数组最值类二分问题的解题框架可以归纳为四条明确解空间初始为[0, n-1]循环条件l r最终l收敛到最小值下标选取比较基准与右端点nums[r]比较判定 mid 归属不要与左端点比较防死循环mid 向下取整收缩右边界用r mid收缩左边界用l mid 1提前退出nums[l] nums[r]时区间整体有序直接返回nums[l]。同时务必牢记仓库二分讲义 thinkings/binary-search-2.md二分专题下篇反复强调的结论有无重复元素对二分算法影响很大。无重复时 153 题可以稳定做到O(log n)引入重复后 154 题在最坏情况下退化为O(n)且必须通过相等时舍弃右端点来处理nums[mid] nums[r]的歧义局面。如需继续练习同类题目可参考仓库 91/binary-search.md 题目推荐中的 875. 爱吃香蕉的珂珂等能力检测二分题以及 33. 搜索旋转排序数组这一旋转数组找指定值的姊妹题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

二分查找求旋转排序数组最小值：153 题解深度拆解与 154 重复元素进阶

相关推荐

详解半导体集成电路QML认证：从MIL-PRF-38535到全流程落地

Chrome插件开发工具选型：同一把 TaoToken Key，从豆包切到 Codex 问

StarRocks CREATE ANALYZE 完全指南：自定义 CBO 统计信息自动采集任务

更多资讯

AIGC新手入门：5分钟快速注册与使用指南

Flutter鸿蒙适配内存问题排查：从黑屏白屏到OOM闪退实战

数据结构从理论到代码：手写链表、二叉树、哈希表与调试实战

ComfyUI云端GPU部署全攻略：从选卡到工作流调优

嵌入式衣物护理机选购指南与热门机型测评

OpenClaw架构解析：LLM与工具调用的工程实践

今日更新

校园网认证计费模式详解：AAA与代拨架构、原理及排障

Spring Boot+Vue垃圾分类毕设：分层、权限与排错实战

把 Cline 的 Base URL 改到 TaoToken 之后，DeepSeek 仍能修调试配置

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？