LeetCode 第 4 题：“寻找两个有序数组的中位数”题解
题解地址：二分查找短数组的“边界线”，长数组的“边界线”自动确定（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：4. 寻找两个有序数组的中位数。
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3] nums2 = [2]
则中位数是 2.0 示例 2:
nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
二分查找短数组的“边界线”，长数组的“边界线”自动确定（Python 代码、Java 代码）
方法一：根据定义，合并、排序以后取中位数（时间复杂度不符合要求）
这应该是最简单直接的做法，即根据定义来做。考虑如下两种情况：
情况 1：如果合并以后的数组的长度是偶数，中位数有 2 个，此时取它们的平均值；
情况 2：如果合并以后的数组的长度是奇数；中位数有 1 个，把这个值返回即可。
说明：这个解法虽然不符合题目要求，但是是常规思路。并且它的优点也很显著：即在输入数组不是有序数组的时候，这个算法依然有效，因此如果这一题出现在面试中，向面试官提到这个最简单的思路，我觉得也是有必要的（一定要把它的这个优点连带说出来）。
参考代码 1：
Python 代码：
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
nums1.extend(nums2)
nums1.sort()
if (m + n) & 1:
return nums1[(m + n - 1) >> 1]
else:
return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2
Java 代码：
import java.util.Arrays;
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] merge = new int[m + n];
System.arraycopy(nums1, 0, merge, 0, m);
System.arraycopy(nums2, 0, merge, m, n);
Arrays.sort(merge);
if (((m + n) & 1) == 1) {
return merge[(m + n - 1) >>> 1];
} else {
return (double) (merge[(m + n - 1) >>> 1] + merge[(m + n) >>> 1]) / 2;
}
}
}
复杂度分析：
- 时间复杂度：，这里 是数组 nums1 的长度， 是数组 nums2 的长度。
- 空间复杂度：。
分析：
优点：
1、简单、直接，编码出错的概率低；
2、在输入数组是非有序数组的时候，算法依然有效。
缺点：
1、空间复杂度高：这个算法连排序都做好了，得使用两个数组的长度之和的空间；
2、时间复杂度高：得看完所有的两个数组的数。
根据以上分析的两个缺点，在思路上我们有如下优化：我们可以不用拼在一起再排序，使用“归并排序的子过程”也可以得到一个更长的有序数组，从而得到这个更长的有序数组的中位数。
可以在「力扣」第 88 题：合并两个有序数组的题解《思路没有创新的地方，主要提供逻辑清楚的代码和编码细节（Python 代码、Java 代码）》中看到如何归并两个有序数组。不过我们没有必要搞一个新数组真的去合并，设置两个指针在数组上移动即可。仔细思考过后，还发现实际上没有必要“归并”完全，在归并的时候，我们只要看完排在前面的一半的数就可以了。
方法二：使用“归并排序”的子过程（时间复杂度不符合要求）
数组长度之和是奇数的时候，要看到索引为 \cfrac{m - 1}{2} 的这个数， 数组长度之和是偶数时，要看到索引为 \cfrac{m}{2} 的这个数。
有两种思路：
- 思路1（不采用）：
不管长度之和是奇数还是偶数，直接先看到索引为 \cfrac{m - 1}{2} 的这个数，如果是奇数，就可以返回了，如果是偶数，再往下看一个数；
编码的时候，发现，会有一些冗余的代码，并且要考虑一些边界的问题，例如看索引为 \cfrac{m}{2} 的数的时候，可能 nums1 和 nums2 其中之一已经看完。
- 思路2（采用）：
那么不管奇数偶数，我都看到索引为 \cfrac{m}{2} 的这个数，那么索引为 \cfrac{m - 1}{2} 的这个数肯定看过了。
技巧：
1、我只关心最近看到的这两个数，那么我不妨将它们放置在一个长度为 的数组中，使用计数器模 的方式计算索引（这个技巧貌似叫做“滚动变量”），这样空间复杂度就可以降到常数。
2、在编码的时候，使用 counter 这个指针表示最后一次赋值的那个索引，初始化的时候，应该为 ，在每一次循环开始之前 ++ 。
参考代码 2：
Python 代码：
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
# 最后要找到合并以后索引是 median_index 的这个数
median_index = (m + n) >> 1
# nums1 的索引
i = 0
# nums2 的索引
j = 0
# 计数器从 -1 开始，在循环开始之前加 1
# 这样在退出循环的时候，counter 能指向它最后赋值的那个元素
counter = -1
res = [0, 0]
while counter < median_index:
counter += 1
# 先写 i 和 j 遍历完成的情况，否则会出现数组下标越界
if i == m:
res[counter & 1] = nums2[j]
j += 1
elif j == n:
res[counter & 1] = nums1[i]
i += 1
elif nums1[i] < nums2[j]:
res[counter & 1] = nums1[i]
i += 1
else:
res[counter & 1] = nums2[j]
j += 1
# print(res)
# 每一次比较，不论是 nums1 中元素出列，还是 nums2 中元素出列
# 都会选定一个数，因此计数器 + 1
# 如果 m + n 是奇数，median_index 就是我们要找的
# 如果 m + n 是偶数，有一点麻烦，要考虑其中有一个用完的情况，其实也就是把上面循环的过程再进行一步
if (m + n) & 1:
return res[counter & 1]
else:
return sum(res) / 2
Java 代码：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 最后要找到合并以后索引是 median_index 的这个数
int medianIndex = (m + n) >>> 1;
// 计数器从 -1 开始，在循环开始之前加 1
// 这样在退出循环的时候，counter 能指向它最后赋值的那个元素
int counter = -1;
// nums1 的索引
int i = 0;
// nums2 的索引
int j = 0;
int[] res = new int[]{0, 0};
while (counter < medianIndex) {
counter++;
// 先写 i 和 j 遍历完成的情况，否则会出现数组下标越界
if (i == m) {
res[counter & 1] = nums2[j];
j++;
} else if (j == n) {
res[counter & 1] = nums1[i];
i++;
} else if (nums1[i] < nums2[j]) {
res[counter & 1] = nums1[i];
i++;
} else {
res[counter & 1] = nums2[j];
j++;
}
}
// 如果 m + n 是奇数，median_index 就是我们要找的
// 如果 m + n 是偶数，有一点麻烦，要考虑其中有一个用完的情况，其实也就是把上面循环的过程再进行一步
if (((m + n) & 1) == 1) {
return res[counter & 1];
} else {
return (double) (res[0] + res[1]) / 2;
}
}
}
复杂度分析：
- 时间复杂度：，这里 是数组 nums1 的长度， 是数组 nums2 的长度，看了数组长度之和的一半，常数系数视为 。
- 空间复杂度：，这里候选值数组
res只占 个空间，用到的其它辅助变量也只有常数个。
接下来的这个思路是符合题目对时间复杂度要求的，但是我个人觉得偏难。它的优点当然在于时间复杂度低，能够很快胜任，但这个算法不一定好。
1、编码较困难，得考虑清楚不同的边界情况，因此编码出错的概率很高；
2、调试困难，出了什么问题，自己调试起来也未必很快就能找到原因，尤其是在一些边界条件的时候（这道题的边界条件在下面这个 PPT 的第 5 张，我画了 6 张图）；
3、相对于方法一：在输入数组如果不是有序数组的话，该算法失效。
因此，也不是非常好的算法，处处都“碾压”一个看起来比较不怎样的算法，简单、好想的算法也有它的用武之地，要针对具体的场景选择使用不同的方法。
下面这个方法是我看了很多朋友的题解，最终在 LeetCode 的英文版的官方题解一个评论里看到的思路和代码，思路我是用自己的话写了出来，希望能够对大家有所帮助。
思路很简单，找两个有序数组的分割。编码上有一点点技巧，特别是在处理边界条件的时候。
我个人觉得这样的问题看别人的题解的时候，先看个大概，懂得大致的思路，这相当于接受了他人的提示，然后尝试自己编码能不能做出来。然后还有一点是很重要的，很多算法题我都是得在纸上打个草稿，才能把思路和边界条件想清楚明白，所以一定不能偷懒。
方法三：使用二分法找两个数组的“边界线”
（温馨提示：下面的幻灯片建议您点击右下角的前进 “▶|” 或者后退 “|◀” 按钮以控制播放。）
参考代码 3：使用《“神奇的”二分查找法模板》写出的代码，使用这个模板会快一点点，但是用不好的话，比较容易采坑，如果不熟悉这个模板的朋友，可以直接跳到“参考代码 4”。
Python 代码：
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
if len(nums1) > len(nums2):
# 这里使用了 pythonic 的写法，即只有在 Python，中可以这样写
# 在一般的编程语言中，得使用一个额外变量，通过"循环赋值"的方式完成两个变量的地址的交换
nums1, nums2 = nums2, nums1
# 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
m = len(nums1)
n = len(nums2)
# 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
left = 0
right = m
# 因为 left_total 这个变量会一直用到，因此单独赋值，表示左边粉红色部分一共需要的元素个数
left_total = (m + n + 1) >> 1
while left < right:
# 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
# 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
# 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
i = (left + right) >> 1
j = left_total - i
# 如果 nums1 左边最大值 > nums2 右边最小值
if nums2[j - 1] > nums1[i]:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
left = i + 1
else:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
# 【注意】：不让它收缩的原因是讨论 nums1[i - 1] > nums2[j]，i - 1 在数组的索引位置，在 i = 0 时越界
right = i
# 退出循环的时候，交叉小于等于一定关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
i = left
j = left_total - left
# 边界值的特殊取法的原因在 PPT 第 10 张
nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
nums2_right_min = float('inf') if j == n else nums2[j]
# 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
if (m + n) & 1:
return max(nums1_left_max, nums2_left_max)
else:
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2
Java 代码：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
// 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
int m = nums1.length;
int n = nums2.length;
// 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
int left = 0;
int right = m;
// 这里使用的是最简单的、"传统"的二分查找法模板，使用"高级的"二分查找法模板在退出循环时候处理不方便
while (left <= right) {
// 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
// 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
// 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
int i = (left + right) >>> 1;
// j 的取值在 PPT 第 7 张
int j = ((m + n + 1) >>> 1) - i;
// 边界值的特殊取法的原因在 PPT 第 10 张
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];
// 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
if (((m + n) & 1) == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
}
} else if (nums2LeftMax > nums1RightMin) {
// 这个分支缩短边界的原因在 PPT 第 8 张
left = i + 1;
} else {
// 这个分支缩短边界的原因在 PPT 第 8 张
right = i - 1;
}
}
throw new IllegalArgumentException("传入无效的参数，输入的数组不是有序数组，算法失效");
}
}
参考代码 4：使用“传统的”二分查找法模板写出的代码。
Python 代码：
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
if len(nums1) > len(nums2):
# 这里使用了 pythonic 的写法，即只有在 Python，中可以这样写
# 在一般的编程语言中，得使用一个额外变量，通过"循环赋值"的方式完成两个变量的地址的交换
nums1, nums2 = nums2, nums1
# 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
m = len(nums1)
n = len(nums2)
# 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
left = 0
right = m
# 这里使用的是最简单的、"传统"的二分查找法模板
while left <= right:
# 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
# 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
# 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
i = (left + right) >> 1
j = ((m + n + 1) >> 1) - i
# 边界值的特殊取法的原因在 PPT 第 10 张
nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
nums2_right_min = float('inf') if j == n else nums2[j]
# 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
# 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
if (m + n) & 1:
return max(nums1_left_max, nums2_left_max)
else:
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2
elif nums1_left_max > nums2_right_min:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
right = i - 1
else:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
left = i + 1
raise ValueError('传入无效的参数，输入的数组不是有序数组，算法失效')
Java 代码：
public class Solution4 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
// 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
int m = nums1.length;
int n = nums2.length;
// 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
int left = 0;
int right = m;
// 因为 left_total 这个变量会一直用到，因此单独赋值，表示左边粉红色部分一共需要的元素个数
int totalLeft = (m + n + 1) >>> 1;
while (left < right) {
// 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
// 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
// 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
int i = (left + right) >>> 1;
// j 的取值在 PPT 第 7 张
int j = totalLeft - i;
if (nums2[j - 1] > nums1[i]) {
// 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
left = i + 1;
} else {
// 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
// 【注意】：不让它收缩的原因是讨论 nums1[i - 1] > nums2[j]，i - 1 在数组的索引位置，在 i = 0 时越界
right = i;
}
}
// 退出循环的时候，交叉小于等于一定关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
int i = left;
int j = totalLeft - left;
// 边界值的特殊取法的原因在 PPT 第 10 张
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];
// 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
// 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
if (((m + n) & 1) == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
}
}
}
复杂度分析：
- 时间复杂度：，为了使得搜索更快，我们把更短的数组设置为 nums1 ，因为使用二分查找法，在它的长度的对数时间复杂度内完成搜索。
- 空间复杂度：，只使用了常数个的辅助变量。