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

二分彻底吃透：以「旋转排序数组的最小值」为例

news 2026/5/11 20:46:57

这篇文章通过一道经典题目：LeetCode 153「Find Minimum in Rotated Sorted Array」，从零拆解二分搜索的两大模板、区间含义，以及为什么会出现各种"神秘"的条件，例如 while (left < right)、right = mid 这种看起来不直观的写法。leetcode+1

题目回顾

题意简述：

有一个严格递增的有序数组，被旋转了若干次（1 到 n 次）。
数组中的元素互不相同。
要求在 O(log⁡n)O(\log n)O(logn) 时间内找出数组中的最小值。algo+1

典型例子：

[0,1,2,4,5,6,7] → 旋转 4 次 → [4,5,6,7,0,1,2]，最小值是 0
[11,13,15,17] → 旋转 4 次 → 还是 [11,13,15,17]，最小值是 11（其实没变）leetcode

直观思路：找「跳变点」

从直觉上看，最小值就是"从大突然变小"的那个位置，也就是拐点 / 跳变点：

在原始升序数组中不存在这种"下降"；
旋转之后，只会出现一次从大到小的跳变，这个位置就是最小值。

因此，一个自然的想法是：

默认最小值在 nums[0]。
用二分找一个 mid，判断它是不是跳变点：
- 如果 nums[mid - 1] > nums[mid] 且 nums[mid + 1] > nums[mid]，那 mid 就是最小值。
- 否则，通过比较决定向左还是向右缩小区间。

这个方向在"思维上"没有问题，但在具体实现上会遇到几个麻烦：

要访问 mid - 1 / mid + 1，很容易在 mid == 0 或 mid == n - 1 时越界。
条件会比较复杂，不够稳定和通用。
面试里更推荐的是一套更简洁、更稳定的模板化写法。

二分的两套经典模板

理解这道题之前，先把二分的两种常见模板说清楚。stackoverflow+2

模板一：存在性查询 while (left <= right)

典型用于：“数组里有没有 target？返回下标；没有就返回 -1”。geeksforgeeks+1

伪代码：

intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target){returnmid;// 找到直接返回}elseif(nums[mid]<target){left=mid+1;// 排除掉 mid 以及左边}else{right=mid-1;// 排除掉 mid 以及右边}}return-1;// 跑完 while 表示没找到}

特征：

区间是闭区间 [left, right]，表示 target 可能存在于其中。
nums[mid] == target 时在循环内部直接 return。
每次更新都是 mid ± 1，把 mid 本身从区间中移除。
循环结束时一定是 left > right，因为最后一次 left == right 那轮已经在 while 里消耗掉了。
- 要么在那一轮找到并 return；
- 要么那一轮之后变成 left = right + 1 或 right = left - 1，也就是 left > right。stackoverflow+1
这就是为什么这种模板的"结束状态"是 left > right 而不是 left == right。

模板二：收缩到一个点 while (left < right)

典型用于：找边界、找最小值、找第一个/最后一个满足条件的位置，本题就属于这一类。labuladong+1

伪代码通用形式：

intleft=0,right=n-1;while(left<right){intmid=left+(right-left)/2;if(某个条件成立){// 最小值在 mid 右侧left=mid+1;}else{// 最小值在左侧，包括 mid 本身right=mid;}}// 循环结束时：left == rightreturnleft;// 或 nums[left]

特征：

区间仍然是闭区间 [left, right]，表示答案一定在这个区间中。
循环目标不是"找到就返回"，而是把区间不断缩小，直到只剩一个位置。
循环条件是 left < right，因此退出时必然是 left == right。
整个过程中始终维护 left <= right，不会出现 left > right。w3tutorials+1

回到本题：为什么是 right = mid 而不是 right = mid - 1

这道题的经典写法（你已经写出来了）是：

intfindMin(int*nums,intnumsSize){intleft=0,right=numsSize-1;// 如果本来就是有序且没旋转，直接返回最左if(nums[left]<nums[right])returnnums[left];while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[right]){// 最小值一定在 mid 右边left=mid+1;}else{// 最小值在左边，包含 mid 自己right=mid;}}returnnums[left];}

关键就在 else 分支这句：为什么是 right = mid，而不是 left = mid 或 right = mid - 1？geeksforgeeks+1

思路拆解

nums[mid] > nums[right]：
- 右端 right 所在的这一段是"被旋转后的尾部"，比前面那段小。
- 如果 mid 这一点比 right 还大，说明 mid 一定在"左边那段较大的递增区间里"，最小值一定在 mid 右边。
- 所以安全地排除掉 mid 以及其左边，写成：left = mid + 1。read.learnyard+1
nums[mid] <= nums[right]（也就是 else）：
- 说明从 mid 到 right 这一段是"整体有序且数值偏大的一截"，最小值不可能在 mid 右边。
- 此时最小值要么在 mid，要么在 mid 左边。
- 因此 mid 是一个合法的候选位置，不能被排除。
- 为了继续二分，缩小区间，同时保留 mid，只能写：right = mid。algo+1

如果你写成：

right = mid - 1：会把 mid 排除掉，而这一支的含义正是"最小值有可能在 mid"，排除掉会漏解。
left = mid：在 left < right 时，mid 可能等于 left，这样会导致区间不变，形成死循环。

从「区间语义」看这件事

这一整套写法的核心不在于具体比较，而在于始终维护这样一个不变式：

在任意时刻，最小值一定在 [left, right] 这个区间内。

于是：

在排除右侧时，要用 left = mid + 1，因为最小值不可能在 mid 以及左边。
在排除左侧时，要用 right = mid 而不是 right = mid - 1，因为最小值有可能就是 mid。

而 while (left < right) 配合这样的更新方式，保证区间大小严格缩小，最终收敛到 left == right 这个唯一的候选位置。vultr+1

再看一眼完整代码

这是你通过题目的 C 代码，已经是教科书式写法：

intfindMin(int*nums,intnumsSize){intleft,right,mid;left=0;right=numsSize-1;if(nums[left]<nums[right])returnnums[left];while(left<right){mid=left+(right-left)/2;if(nums[mid]>nums[right])left=mid+1;elseright=mid;}returnnums[left];}