数组二分搜索变体：旋转数组与中位数
摘要
二分搜索的”基础版”——在有序数组里找一个数——很多人都会写。但面试中真正有区分度的是它的变体：旋转数组（33、81 题）和两个有序数组的中位数（4 题）。这三道题是二分搜索思维的试金石，难在”有序性被破坏了怎么办”以及”二分的对象不是元素而是答案区间”。本文从二分搜索的本质出发，建立一套能应对所有变体的思维框架，不再靠死记边界条件，而靠逻辑推导得出正确代码。
第 1 章 二分搜索的本质：每次排除一半
1.1 不是”找到答案”，而是”缩小范围”
初学者理解二分搜索的常见误区：觉得二分是”每次猜中间那个，猜中了就找到了”。这个理解本质上没错，但不够深刻，导致遇到变体题时无法迁移。
更准确的理解是：二分搜索的每一步，不是要”找到答案”，而是要”证明某一半区间不可能包含答案”，从而把搜索范围缩小一半。
这个视角的转变非常重要。比如在旋转数组里搜索，你乍一看可能觉得”乱的，怎么二分”，但如果你问的是”哪一半区间可以被安全排除”，思路就豁然开朗了。
1.2 二分模板与边界条件
二分搜索的边界条件是无数人的噩梦。是 left < right 还是 left <= right？是 mid+1 还是 mid？本专栏使用一套统一的模板，配合不变量理解，彻底根除混乱。
闭区间模板（左闭右闭 [left, right]）：
int left = 0, right = nums.length - 1;
while (left <= right) { // 区间非空时继续
int mid = left + (right - left) / 2; // 防溢出写法，等价于 (left+right)/2
if (nums[mid] == target) {
return mid; // 找到，直接返回
} else if (nums[mid] < target) {
left = mid + 1; // mid 已经检查过且不是答案，排除 [left, mid]
} else {
right = mid - 1; // 同理，排除 [mid, right]
}
}
return -1; // 未找到关键逻辑：
left <= right：循环条件保证区间[left, right]非空（left > right时区间空，没必要继续）left = mid + 1/right = mid - 1：mid已经被检查且不是答案，所以新区间排除mid本身mid = left + (right - left) / 2：当left + right可能溢出 int 范围时的安全写法
生产避坑：整数溢出
在 Java 中
int最大值是约 21 亿（）。如果left和right都接近 21 亿，left + right会溢出变成负数。虽然 LeetCode 的测试数据一般不会触发这个问题，但在面试中写出防溢出写法是工程素养的体现。
第 2 章 LeetCode 33：搜索旋转排序数组
2.1 题目
LeetCode 33 - Search in Rotated Sorted Array（中等）
整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k 处进行了旋转（例如，[0,1,2,4,5,6,7] 在下标 3 处旋转变成了 [4,5,6,7,0,1,2]）。
给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。
要求时间复杂度 。
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
2.2 旋转数组的结构分析
旋转之后，原来完整的升序数组被切成了两段，每段内部仍然是升序的。以 [4,5,6,7,0,1,2] 为例：
旋转点
↓
[4, 5, 6, 7, | 0, 1, 2]
左侧升序段 右侧升序段
最小值=4 最小值=0
最大值=7 最大值=2
关键观察：对于任意中间下标 mid，[left, mid] 和 [mid+1, right] 这两段中，至少有一段是完全有序的。
证明：旋转点（从大到小的跳变处）在整个数组中只有一个。那么对于区间 [left, right]，中间切一刀后，旋转点要么落在左半段，要么落在右半段，要么恰好在 mid 处——但无论如何，另一半必然是完全有序的。
这个观察是解题的核心突破口。
2.3 算法思路
基于上面的分析，在每次迭代中：
第一步：判断哪一半是有序的。
- 如果
nums[left] <= nums[mid]：左半段[left, mid]是有序的 - 否则：右半段
[mid+1, right]是有序的（因为左半段包含旋转点，右半段必然有序）
第二步：判断 target 是否在有序的那一半。
- 如果 target 落在有序区间的范围内，就在那一半继续搜索
- 否则，在另一半搜索
为什么这样判断有效？只有有序区间才能用 nums[left] <= target <= nums[mid] 这种范围判断。无序区间无法做范围判断，无法确定 target 是否在其中。
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
// 左半段 [left, mid] 是有序的
if (nums[left] <= target && target < nums[mid]) {
// target 在左半段的范围内，去左半段搜
right = mid - 1;
} else {
// target 不在左半段，去右半段
left = mid + 1;
}
} else {
// 右半段 [mid, right] 是有序的
if (nums[mid] < target && target <= nums[right]) {
// target 在右半段的范围内，去右半段搜
left = mid + 1;
} else {
// target 不在右半段，去左半段
right = mid - 1;
}
}
}
return -1;
}2.4 手动模拟
以 nums = [4,5,6,7,0,1,2], target = 0 为例：
初始: left=0, right=6
[4, 5, 6, 7, 0, 1, 2]
0 1 2 3 4 5 6
迭代1: mid=3, nums[3]=7 ≠ 0
nums[left=0]=4 <= nums[mid=3]=7 → 左半段 [0,3] 有序
target=0 在 [4,7] 范围内吗？4<=0? 否 → 去右半段
left = mid+1 = 4
迭代2: left=4, right=6, mid=5, nums[5]=1 ≠ 0
nums[left=4]=0 <= nums[mid=5]=1 → 左半段 [4,5] 有序
target=0 在 [0,1) 内吗？0<=0 且 0<1？是 → 去左半段
right = mid-1 = 4
迭代3: left=4, right=4, mid=4, nums[4]=0 == target → 返回 4
2.5 边界细节解析
为什么用 nums[left] <= nums[mid] 而不是 <？
当 left == mid（区间只有一个元素）时，nums[left] == nums[mid]，此时左半段”有序”（只有一个元素的序列当然有序），用 <= 可以正确覆盖这种情况。
内层条件 nums[left] <= target && target < nums[mid] 为什么是 < 而不是 <=？
因为前面已经检查了 nums[mid] == target 并直接返回了，所以走到这里时 nums[mid] != target，所以条件里 target < nums[mid] 是正确的（等号情况已经排除）。
第 3 章 LeetCode 81：搜索旋转排序数组 II（含重复元素）
3.1 题目
LeetCode 81 - Search in Rotated Sorted Array II（中等）
与第 33 题相同，但数组中可以有重复元素，返回 boolean（是否存在 target）。
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
3.2 重复元素带来的新困境
第 33 题之所以能靠 nums[left] <= nums[mid] 判断哪半段有序，前提是元素不重复。有了重复元素，会出现什么情况？
考虑 [1, 1, 1, 3, 1]：
left=0, right=4, mid=2nums[left]=1, nums[mid]=1，满足nums[left] <= nums[mid]- 按照第 33 题的逻辑，我们会认为左半段
[0,2]有序（确实有序，全是 1） - 但如果
target=3，我们会认为 3 不在[1,1]范围内，去右半段搜索 - 右半段
[3,4]是[3,1]，可以找到 3，正确
再考虑 [3, 1, 1]：
left=0, right=2, mid=1nums[left]=3, nums[mid]=1，满足nums[left] > nums[mid]- 按照第 33 题的逻辑，右半段
[1,2]有序 - 如果
target=3，3 不在[1,1]范围内，去左半段，可以找到，正确
真正麻烦的情况：[1, 3, 1, 1, 1]：
left=0, right=4, mid=2nums[left]=1 == nums[mid]=1- 我们无法判断左半段还是右半段是有序的！
- 旋转点可能在左半段（如
[1,3,1,...]，3后面跳小） - 旋转点也可能在右半段（如
[...,1,1,1]，没有旋转）
- 旋转点可能在左半段（如
当 nums[left] == nums[mid] 时，无法确定哪半段有序，二分失效。
3.3 解决方案：退化为线性扫描
当无法判断时，采用保守策略：left++（缩小左边界，跳过一个重复元素，下次再判断）。这会让最坏情况下的复杂度退化到 （全部是重复元素时，每次只能排除一个），但平均情况仍然接近 。
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// 关键：处理重复元素导致无法判断哪半有序的情况
if (nums[left] == nums[mid]) {
left++; // 无法判断，左指针右移一步，跳过重复元素
continue;
}
if (nums[left] < nums[mid]) {
// 左半段有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 右半段有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}设计哲学：不完美的二分也是二分
第 81 题的核心教训是：当标准的二分条件无法成立时，退而求其次（
left++，每次只排除一个元素），接受最坏情况下的性能退化，换取算法的正确性。这是工程权衡的典型例子——追求完美的 可能导致错误答案，不如用一个稍差但正确的方案。
第 4 章 LeetCode 4：寻找两个正序数组的中位数
4.1 题目
LeetCode 4 - Median of Two Sorted Arrays（困难）
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
要求算法的时间复杂度为 。
输入: nums1 = [1,3], nums2 = [2]
输出: 2.0（中位数是 2）
输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.5（中位数是 (2+3)/2 = 2.5）
4.2 为什么这道题是”困难”级别
如果没有时间复杂度要求，合并两个有序数组（归并排序的一步），然后找中位数，是 的，代码也不难。
困难在于 的要求。 级别意味着必须用二分，但二分什么？我们不能简单地在某一个数组上二分，因为中位数可能涉及两个数组的元素。
关键洞察：中位数的本质是”把所有 个元素分成等长的两组，左组的最大值 ≤ 右组的最小值”。
4.3 核心思路：二分”划分位置”
设两个数组总长度为 total = m + n，中位数把所有元素分成左右两半，左半部分有 half = (total + 1) / 2 个元素（+1 是为了处理总数为奇数时左边多一个的情况）。
我们的目标：在 nums1 中找一个划分点 i（左边取 i 个元素），在 nums2 中找一个划分点 j（左边取 j 个元素），使得 i + j == half，且满足：
（即左半部分的最大值 ≤ 右半部分的最小值）
nums1: [... | nums1[i-1] | nums1[i] ...]
左边取 i 个 右边剩余
nums2: [... | nums2[j-1] | nums2[j] ...]
左边取 j 个 右边剩余
条件: nums1[i-1] <= nums2[j] （nums1 左边最大 ≤ nums2 右边最小）
nums2[j-1] <= nums1[i] （nums2 左边最大 ≤ nums1 右边最小）
由于 j = half - i，只要对 i 进行二分，j 就自动确定了。我们对 i 在 [0, m] 范围内二分（i 可以是 0 表示 nums1 一个都不选，m 表示全选）。
如何调整 i？
- 如果
nums1[i-1] > nums2[j]：说明nums1的左边选多了（选了一个太大的进左组），需要减小i（right = i - 1） - 如果
nums2[j-1] > nums1[i]：说明nums1的左边选少了，需要增大i（left = i + 1）
4.4 完整代码实现
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 确保 nums1 是较短的数组，减少二分范围
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length, n = nums2.length;
int half = (m + n + 1) / 2; // 左半部分应有的元素数
int left = 0, right = m; // 对 nums1 的划分点 i 进行二分，范围 [0, m]
while (left <= right) {
int i = left + (right - left) / 2; // nums1 左边取 i 个
int j = half - i; // nums2 左边取 j 个（自动确定）
// 获取四个边界值（处理越界情况：0 个时用 -∞，全取时用 +∞）
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (nums1LeftMax > nums2RightMin) {
// nums1 左边选多了，i 需要减小
right = i - 1;
} else if (nums2LeftMax > nums1RightMin) {
// nums1 左边选少了，i 需要增大
left = i + 1;
} else {
// 找到了正确的划分！
int maxLeft = Math.max(nums1LeftMax, nums2LeftMax);
int minRight = Math.min(nums1RightMin, nums2RightMin);
if ((m + n) % 2 == 1) {
// 总数为奇数，中位数是左半部分的最大值
return maxLeft;
} else {
// 总数为偶数，中位数是左半最大值和右半最小值的平均
return (maxLeft + minRight) / 2.0;
}
}
}
return 0.0; // 不会到达这里
}4.5 手动验证
例 1：nums1 = [1, 3]，nums2 = [2]
m=2, n=1, half=2- 二分
i在[0, 2]：i=1, j=1：nums1LeftMax=1, nums1RightMin=3, nums2LeftMax=2, nums2RightMin=MAX- 检查：
1 <= MAX且2 <= 3，条件满足！ (m+n)%2 = 3%2 = 1（奇数），返回maxLeft = max(1, 2) = 2✓
例 2：nums1 = [1, 2]，nums2 = [3, 4]
m=2, n=2, half=2- 二分
i在[0, 2]：i=1, j=1：nums1LeftMax=1, nums1RightMin=2, nums2LeftMax=3, nums2RightMin=4- 检查：
nums2LeftMax=3 > nums1RightMin=2→left = i+1 = 2 i=2, j=0：nums1LeftMax=2, nums1RightMin=MAX, nums2LeftMax=MIN, nums2RightMin=3- 检查：
2 <= 3且MIN <= MAX，条件满足！ (m+n)%2 = 0（偶数），返回(max(2, MIN) + min(MAX, 3)) / 2.0 = (2+3)/2.0 = 2.5✓
4.6 为什么要确保 nums1 是较短的数组
代码的第一行：
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}这是因为我们对 i（nums1 的划分点）进行二分，i 的范围是 [0, m]，也就是 m+1 个可能值。同时 j = half - i，j 必须满足 0 <= j <= n，即 j 不能越界。
如果 nums1 比 nums2 长，可能出现 j = half - i < 0（当 i 太大时）或 j > n（当 i 太小时）的情况，需要额外处理。通过确保 m <= n，可以保证对于任意 i ∈ [0, m]，都有 j = half - i ∈ [0, n]，不会越界，代码更简洁。
第 5 章 二分搜索的横向扩展
5.1 寻找旋转点（最小值）：LeetCode 153/154
第 33 题的一个前置子问题是：找出旋转数组中的最小值（LeetCode 153）。这同样是二分的经典应用：
- 如果
nums[mid] > nums[right]：最小值在[mid+1, right]中（左半段升序且都大于右半段的元素） - 否则：最小值在
[left, mid]中
有了最小值的下标，就知道了旋转点，可以把旋转数组”还原”成两段有序数组来处理。
5.2 二分答案（搜索的对象不是数组元素）
二分的对象不局限于数组元素。对于某类”求最优值”的问题，可以对答案本身进行二分：猜一个答案 mid，验证”答案 ≤ mid 是否可行”，根据验证结果缩小范围。这类技巧在 LeetCode 中属于高阶题型，不在本专栏讨论范围内，但了解其存在有助于建立完整的二分知识体系。
5.3 三道题的复杂度对比
| 题目 | 时间复杂度 | 空间复杂度 | 关键技巧 |
|---|---|---|---|
| LeetCode 33（无重复旋转） | 每次确定哪半段有序，二分 | ||
| LeetCode 81（有重复旋转） | 均摊，最坏 | 重复时退化为 left++ | |
| LeetCode 4（双数组中位数） | 二分划分点而非元素 |
下一篇预告
04 哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence 将进入哈希表辅助数组操作的主题。Two Sum 是面试中频率最高的题目之一，几乎每家公司都考过；而 Longest Consecutive Sequence 则是一道反直觉的题——看起来需要排序（），实际上用哈希可以做到 。