# 题目描述：
给定两个大小为 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
# 方法：递归法
为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
如果理解了中位数的划分作用，我们就很接近答案了。
首先，让我们在任一位置 i 将 A 划分成两个部分：
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于 $ \text{A}$ 中有 m 个元素， 所以我们有 m+1 种划分的方法 （i=0∼m）。
我们知道：
len(left_A)=i,len(right_A)=m−i.
.
注意：当 $ i = 0$ 时，\text{left_A}left_A 为空集， 而当 i = mi=m 时, \text{right_A}right_A 为空集。
采用同样的方式，我们在任一位置 j 将 B 划分成两个部分：
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
将 left_A和left_B 放入一个集合，并将 right_A 和 right_B 放入另一个集合。
再把这两个新的集合分别命名为 left_part 和 right_part：
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
如果我们可以确认：
len(left_part)=len(right_part)
.
max(left_part)≤min(right_part)
那么，我们已经将 {A,B} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。
那么：
median=2max(leftpart)+min(rightpart)
要确保这两个条件，我们只需要保证：
- i+j=（m−i）+（n−j）【或： （m−i）+（n−j）+1 】<mark>（白话：i、j 这两个切点的左右的数的个数相等）</mark>
如果 n≥m，只需要使 i=0∼m,j=2m+n+1−i （这个推论后面会用到哦）
问题：是否加1的区别？
wsm：后面都是 （m−i）+（n−j）+1？
偶数时候： i+j=（m−i）+（n−j），中位数必然由两个数如a、b虚构出来，因此，我们可以偷偷把虚构出来的数当做原有的数。那么，无论什么情况，处理的都是奇数情况，因此可以统一使用公式： i+j=（m−i）+（n−j）+1- B[j−1]≤A[i] 以及 A[i−1]≤B[j] <mark>（白话：A的右边最小大于B的左边最大，相对的，B的右边最小大于A的左边最大）</mark>
-
ps. 1 为了简化分析，我假设 A[i−1],B[j−1],A[i],B[j] 总是存在，哪怕出现 i=0，i=m，j=0，或是 j=n 这样的临界条件。
我将在最后讨论如何处理这些临界值。 -
ps.2 <mark>为什么 n≥m？</mark>
由于 0≤i≤m ，且 j=2m+n+1−i
⇒ . . . 我必须确保 j 不是负数。如果 n<m，那么 j 将可能是负数 <mark>（如 i=m）</mark>，而这会造成错误的答案。
所以，我们需要做的是：
在 [0，m] 中搜索并找到目标对象 i，以使：
B[j−1]≤A[i] 且 A[i−1]≤B[j],
其中 j=2m+n+1−i
接着，我们可以按照以下步骤来进行二叉树搜索：
0. （前提，让n>m）
// A 、 B 是两个数组
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp; // 交换数组 的对象应用
int tmp = m; m = n; n = tmp; // 交换数组长度 的对象应用
}
int iMin = 0, iMax = m,halfLen = (m + n + 1) / 2; // 一半长度
while (iMin <= iMax) {
//................................... 搜索 ing ..
}
while (iMin <= iMax) {
//................................... 搜索 ing ..
int i = (iMin + iMax) / 2; // 从中间开始找
int j = halfLen - i;
}
bad 情况一：
while (iMin <= iMax) {
//................................... 搜索 ing ..
int i = (iMin + iMax) / 2; // 从中间开始找
int j = halfLen - i;
if (i < iMax && B[j - 1] > A[i]) {
iMin = i+ 1; // i is too small
}
}
bad 情况二：
while (iMin <= iMax) {
//................................... 搜索 ing ..
int i = (iMin + iMax) / 2; // 从中间开始找
int j = halfLen - i;
if (i < iMax && B[j - 1] > A[i]) {
iMin = i+ 1; // i is too small
} else if (i > iMin && A[i - 1] > B[j]) {
iMax = i - 1; // i is too big
}
}
<mark>最好的情况：</mark> i 找到了（base case）
while (iMin <= iMax) {
//................................... 搜索 ing ..
int i = (iMin + iMax) / 2; // 从中间开始找
int j = halfLen - i;
if (i < iMax && B[j - 1] > A[i]) {
iMin = i+ 1; // i is too small
} else if (i > iMin && A[i - 1] > B[j]) {
iMax = i - 1; // i is too big
}else { // i is perfect
// now you can ready to 输出结果 ...
return (maxLeft + minRight) / 2.0;
}
}
找到 i 了，那接下来就可以处理我们之前 避而不谈的细节问题：
1. 临界值？
临界值：i=0
<mark>i=0, 说明 A的数普遍比较大、全部被分在了右边</mark>
..........................
else { // i is perfect
int maxLeft;
if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部) 所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
maxLeft = B[j - 1];
}
.................
临界值：j>0 Or j<n
临界值：j=0
..........................
else { // i is perfect
int maxLeft;
if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部) 所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
maxLeft = B[j - 1];
} else if (j == 0) { //B分成的leftB(空集) 和 rightB(B的全部) 所以leftPart = leftA + leftB(空集),故maxLeft = A[i-1]。
maxLeft = A[i - 1];
}
.................
非临界值：
..........................
else { // i is perfect
int maxLeft;
if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部) 所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
maxLeft = B[j - 1];
} else if (j == 0) { //B分成的leftB(空集) 和 rightB(B的全部) 所以leftPart = leftA + leftB(空集),故maxLeft = A[i-1]。
maxLeft = A[i - 1];
}else { //排除上述两种特殊情况，正常比较
maxLeft = Math.max(A[i - 1], B[j - 1]);
}
.................
- <mark>奇偶？</mark>
..........................
else { // i is perfect
int maxLeft;
if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部) 所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
maxLeft = B[j - 1];
} else if (j == 0) { //B分成的leftB(空集) 和 rightB(B的全部) 所以leftPart = leftA + leftB(空集),故maxLeft = A[i-1]。
maxLeft = A[i - 1];
}else { //排除上述两种特殊情况，正常比较
maxLeft = Math.max(A[i - 1], B[j - 1]);
}
if ((m + n) % 2 == 1) { //奇数，中位数正好是maxLeft
return maxLeft;
}
//偶数
int minRight;
if (i == m) {//A分成的leftA(A的全部) 和 rightA(空集) 所以rightPart = rightA(空集) + rightB,故minRight = B[j]。
minRight = B[j];
} else if (j == n) {//B分成的leftB(B的全部) 和 rightB(空集) 所以rightPart = rightA + rightB(空集),故minRight = A[i]。
minRight = A[i];
} else {//排除上述两种特殊情况，正常比较
minRight = Math.min(B[j], A[i]);
}
return (maxLeft + minRight) / 2.0;
.................
代码
/* * 1.首先，让我们在任一位置 i 将 A(长度为m) 划分成两个部分： * leftA | rightA * A[0],A[1],... A[i-1] | A[i],A[i+1],...A[m - 1] * * 由于A有m个元素，所以有m + 1中划分方式(i = 0 ~ m) * * 我们知道len(leftA) = i, len(rightA) = m - i; * 注意：当i = 0时，leftA是空集，而当i = m时，rightA为空集。 * * 2.采用同样的方式，将B也划分为两部分： * leftB | rightB * B[0],B[1],... B[j-1] | B[j],B[j+1],...B[n - 1] * 我们知道len(leftA) = j, len(rightA) = n - j; * * 将leftA和leftB放入一个集合，将rightA和rightB放入一个集合。再把这两个集合分别命名为leftPart和rightPart。 * * leftPart | rightPart * A[0],A[1],... A[i-1] | A[i],A[i+1],...A[m - 1] * B[0],B[1],... B[j-1] | B[j],B[j+1],...B[n - 1] * * 如果我们可以确认： * 1.len(leftPart) = len(rightPart); =====> 该条件在m+n为奇数时，该推理不成立 * 2.max(leftPart) <= min(rightPart); * * median = (max(leftPart) + min(rightPart)) / 2; 目标结果 * * 要确保这两个条件满足： * 1.i + j = m - i + n - j(或m - i + n - j + 1) 如果n >= m。只需要使i = 0 ~ m，j = (m+n+1)/2-i =====> 该条件在m+n为奇数/偶数时，该推理都成立 * 2.B[j] >= A[i-1] 并且 A[i] >= B[j-1] * * 注意: * 1.临界条件：i=0,j=0,i=m,j=n。需要考虑 * 2.为什么n >= m ? 由于0 <= i <= m且j = (m+n+1)/2-i,必须确保j不能为负数。 * * 按照以下步骤进行二叉树搜索 * 1.设imin = 0,imax = m，然后开始在[imin,imax]中进行搜索 * 2.令i = (imin+imax) / 2, j = (m+n+1)/2-i * 3.现在我们有len(leftPart) = len(rightPart)。而我们只会遇到三种情况： * * ①.B[j] >= A[i-1] 并且 A[i] >= B[j-1] 满足条件 * ②.B[j-1] > A[i]。此时应该把i增大。 即imin = i + 1; * ③.A[i-1] > B[j]。此时应该把i减小。 即imax = i - 1; * * */
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j - 1] > A[i]) {
iMin = i + 1; // i is too small
} else if (i > iMin && A[i - 1] > B[j]) {
iMax = i - 1; // i is too big
} else { // i is perfect
int maxLeft;
if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部) 所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
maxLeft = B[j - 1];
} else if (j == 0) { //B分成的leftB(空集) 和 rightB(B的全部) 所以leftPart = leftA + leftB(空集),故maxLeft = A[i-1]。
maxLeft = A[i - 1];
} else { //排除上述两种特殊情况，正常比较
maxLeft = Math.max(A[i - 1], B[j - 1]);
}
if ((m + n) % 2 == 1) { //奇数，中位数正好是maxLeft
return maxLeft;
}
//偶数
int minRight;
if (i == m) {//A分成的leftA(A的全部) 和 rightA(空集) 所以rightPart = rightA(空集) + rightB,故minRight = B[j]。
minRight = B[j];
} else if (j == n) {//B分成的leftB(B的全部) 和 rightB(空集) 所以rightPart = rightA + rightB(空集),故minRight = A[i]。
minRight = A[i];
} else {//排除上述两种特殊情况，正常比较
minRight = Math.min(B[j], A[i]);
}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
京公网安备 11010502036488号