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

LeetCode 153. 旋转排序数组找最小值：二分最优思路

news 2026/5/11 21:35:24

LeetCode中等难度的经典题目——153. 寻找旋转排序数组中的最小值。这道题的核心考点是「二分查找」，难点在于如何利用“旋转排序数组”的特性，在O(log n)时间复杂度内找到最小值，也是面试中常考的二分变形题。

一、题目解读：读懂旋转排序数组

首先，我们得先搞懂「旋转排序数组」到底是什么。题目里说，原数组是升序排列的，经过1到n次旋转后得到输入数组。这里的“旋转”很简单：每次旋转就是把数组最后一个元素移到最前面。

举个例子更直观：

原升序数组：[0,1,2,4,5,6,7]
旋转4次：把最后一个元素依次移到前面，最终得到 [4,5,6,7,0,1,2]
旋转7次：相当于旋转了一圈，回到原数组 [0,1,2,4,5,6,7]

题目给出的关键条件：数组元素互不相同（这个条件很重要，能简化判断，避免边界陷阱），要求我们找到数组中的最小元素，并且必须设计时间复杂度为O(log n)的算法。

为什么不能用遍历（O(n)）？因为题目明确要求O(log n)，而二分查找的时间复杂度正好是O(log n)，所以这道题的核心思路就是「二分查找」的变形。

二、核心思路：二分查找如何适配旋转数组？

普通二分查找是在有序数组中找目标值，而旋转排序数组的特点是：它被分成了两个升序子数组，且前一个子数组的所有元素都大于后一个子数组的所有元素（比如 [4,5,6,7,0,1,2]，前半段 [4,5,6,7] 升序，后半段 [0,1,2] 升序，且 7 > 0）。

最小值就是这两个子数组的“分界点”——前一个子数组的最后一个元素，后一个子数组的第一个元素。我们的目标就是通过二分查找，快速定位到这个分界点。

二分查找的关键的是「确定边界收缩方向」，这里我们以「中间元素 nums[mid] 和右边界元素 nums[high] 比较」为判断依据，原因很简单：右边界的元素一定属于其中一个升序子数组，能帮我们快速锁定最小值所在的区间。

关键判断逻辑（重中之重）：

如果 nums[mid] < nums[high]：说明 mid 所在的位置，已经在「右半段升序子数组」中（因为右半段是升序的，mid 比 high 小，说明 mid 到 high 都是升序），此时最小值一定在 mid 及其左边，所以收缩右边界：high = mid。
如果 nums[mid] > nums[high]：说明 mid 所在的位置，还在「左半段升序子数组」中（左半段所有元素都比右半段大），此时最小值一定在 mid 的右边，所以收缩左边界：low = mid + 1。

为什么不用 nums[mid] 和 nums[low] 比较？大家可以思考一下：如果数组没有旋转（就是原升序数组），nums[mid] 一定大于 nums[low]，此时最小值在左边，但如果数组旋转了，比如 [3,4,5,1,2]，nums[mid]（5）大于 nums[low]（3），但最小值却在右边，这样判断会出错。所以用 nums[mid] 和 nums[high] 比较是最稳妥的。

三、代码解析：逐行看懂核心逻辑

题目给出的代码非常简洁，只有几行，但每一行都有其作用，我们逐行拆解：

functionfindMin(nums:number[]):number{letlow=0;// 左边界指针，初始指向数组第一个元素lethigh=nums.length-1;// 右边界指针，初始指向数组最后一个元素while(low<high){// 循环条件：左边界 < 右边界（当low == high时，就是最小值所在位置）constmid=Math.floor((high+low)/2);// 计算中间索引（避免溢出，也可以用 (low + high) >> 1）if(nums[mid]<nums[high]){// 中间元素 < 右边界元素，最小值在左区间high=mid;// 收缩右边界到mid（注意不是mid-1，因为mid可能就是最小值）}else{// 中间元素 > 右边界元素，最小值在右区间low=mid+1;// 收缩左边界到mid+1（mid不可能是最小值，直接跳过）}}returnnums[low];// 循环结束后，low == high，就是最小值的索引};

代码细节注意点：

mid 的计算：Math.floor((high + low) / 2) 是最基础的写法，也可以用位运算 (low + high) >> 1（效果相同，效率更高），但要注意避免 low + high 溢出（本题中数组长度不会太大，溢出概率极低）。
循环条件：low < high，而不是 low ≤ high。因为当 low == high 时，已经找到了最小值，循环可以终止，直接返回 nums[low] 即可。
high = mid 而非 mid-1：因为当 nums[mid] < nums[high] 时，mid 有可能就是最小值（比如数组 [2,1]，mid=0，nums[mid]=2 > nums[high]=1，执行 low=mid+1=1，循环结束，返回 nums[1]=1；再比如 [3,1,2]，mid=1，nums[mid]=1 < nums[high]=2，执行 high=mid=1，循环结束，返回 1）。如果写成 high=mid-1，可能会跳过最小值。
low = mid + 1：因为当 nums[mid] > nums[high] 时，mid 一定不是最小值（比如 [4,5,6,7,0,1,2]，mid=3，nums[mid]=7 > nums[high]=2，最小值在 mid 右边，所以直接让 low=mid+1）。

四、考点总结与拓展思考

考点总结：

这道题的核心是「二分查找的变形」，重点考查对“旋转排序数组”特性的理解，以及如何确定二分查找的边界收缩方向。关键在于抓住“旋转数组的两个升序子数组，右半段所有元素小于左半段”这一特点，通过 mid 和 high 的比较，快速锁定最小值所在区间。

时间复杂度：O(log n)，二分查找的经典时间复杂度；空间复杂度：O(1)，只用到了3个变量（low、high、mid），没有额外空间开销。

拓展思考（进阶）：

如果题目修改为「数组元素可能重复」，比如 nums = [2,2,2,0,1]，此时原代码还能生效吗？答案是不能。因为当 nums[mid] == nums[high] 时，我们无法判断最小值在左还是右（比如 [2,0,2,2,2] 和 [2,2,2,0,2]，mid 和 high 都是2，但最小值位置不同）。

这种情况下，我们需要增加一个处理逻辑：当 nums[mid] == nums[high] 时，让 high–（缩小范围，因为重复元素不影响最小值的查找），修改后的代码可以应对元素重复的情况，有兴趣的同学可以自行尝试编写。