寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，找出并返回这两个正序数组的中位数。
要求算法的时间复杂度为 O(log (m + n))。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3]，中位数是 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4]，中位数是 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
二分分割：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
{
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int totalLeft = (m + n + 1) / 2;
int left = 0;
int right = m;
while (left < right)
{
int i = left + (right - left + 1) / 2;
int j = totalLeft - i;
if (nums1[i - 1] > nums2[j])
{
right = i - 1;
}
else
{
left = i;
}
}
int i = left;
int j = totalLeft - i;
int nums1LeftMax = i == 0 ? INT_MIN : nums1[i - 1];
int nums2LeftMax = j == 0 ? INT_MIN : nums2[j - 1];
int nums1RightMin = i == m ? INT_MAX : nums1[i];
int nums2RightMin = j == n ? INT_MAX : nums2[j];
int leftMax = max(nums1LeftMax, nums2LeftMax);
if ((m + n) % 2 == 1)
{
return leftMax;
}
int rightMin = min(nums1RightMin, nums2RightMin);
return (leftMax + rightMin) / 2.0;
}
};
核心思想
如果直接合并两个数组，再取中位数，时间复杂度是 O(m + n)，不满足题目要求。
两个数组本身已经有序，因此可以把问题转化为：
找到一个分割位置，使左半部分元素个数等于中位数左侧所需个数，并且左半部分所有元素都小于等于右半部分所有元素。
设在 nums1 中切出前 i 个元素，在 nums2 中切出前 j 个元素放入左半部分，则必须满足：
i + j = (m + n + 1) / 2
多加的 1 是为了让总长度为奇数时，左半部分比右半部分多一个元素。这样奇数长度的中位数就是左半部分最大值。
分割条件
一次合法分割需要满足：
nums1[i - 1] <= nums2[j]
nums2[j - 1] <= nums1[i]
第一条表示 nums1 左侧最大值不能大于 nums2 右侧最小值。
第二条表示 nums2 左侧最大值不能大于 nums1 右侧最小值。
只要这两条同时成立，左半部分的最大值和右半部分的最小值就能直接确定中位数。
为什么只在较短数组上二分
代码先保证 nums1 是较短的数组：
if (nums1.size() > nums2.size())
{
return findMedianSortedArrays(nums2, nums1);
}
这样二分范围是 [0, m]，复杂度为 O(log m)，也就是 O(log min(m, n))。
同时，因为 nums1 不长于 nums2，由 i + j = totalLeft 推出的 j 更容易保持在合法范围内。
二分查找逻辑
代码二分的是 i，也就是左半部分从 nums1 中取多少个元素。
当：
nums1[i - 1] > nums2[j]
说明 nums1 左侧拿得太多，导致左半部分出现了过大的元素，应该减小 i：
right = i - 1;
否则说明当前 i 不会因为 nums1[i - 1] 太大而非法，可以尝试继续增大 i：
left = i;
循环结束后，i 就是满足 nums1[i - 1] <= nums2[j] 的最大位置。此时另一条条件 nums2[j - 1] <= nums1[i] 也会随之成立，分割合法。
边界处理
分割位置可能出现在数组最左侧或最右侧：
i == 0：表示nums1左半部分为空。i == m：表示nums1全部进入左半部分。j == 0：表示nums2左半部分为空。j == n：表示nums2全部进入左半部分。
为了统一计算，代码使用哨兵值：
INT_MIN
INT_MAX
当某一侧为空时，用 INT_MIN 表示左侧最大值不存在，用 INT_MAX 表示右侧最小值不存在。由于题目中的元素范围远小于 int 边界，这样不会影响比较结果。
如何得到中位数
分割合法后：
int leftMax = max(nums1LeftMax, nums2LeftMax);
int rightMin = min(nums1RightMin, nums2RightMin);
如果总长度为奇数，左半部分比右半部分多一个元素，中位数就是：
leftMax
如果总长度为偶数，中位数是中间两个数的平均值：
(leftMax + rightMin) / 2
正确性证明
结论 1：二分结束后左半部分元素个数正确
算法始终令：
j = totalLeft - i
因此无论二分过程中 i 如何变化，都有：
i + j = totalLeft
所以最终分割后左半部分元素个数一定是中位数所需的数量。
结论 2：二分结束后分割满足有序要求
如果 nums1[i - 1] > nums2[j]，说明 nums1 左侧最大值过大，当前 i 以及更大的 i 都不可能成为合法分割，因此需要向左收缩。
否则当前 i 至少满足第一条分割条件，可以向右寻找更大的可行位置。
循环结束时，i 是满足 nums1[i - 1] <= nums2[j] 的最大位置。若此时 nums2[j - 1] > nums1[i]，则说明还需要从 nums1 中取更多元素，也就是存在更大的合法候选 i，这与当前 i 已经最大矛盾。
因此最终分割同时满足：
nums1[i - 1] <= nums2[j]
nums2[j - 1] <= nums1[i]
即左半部分所有元素都小于等于右半部分所有元素。
结论 3：奇数长度时返回值正确
当总长度为奇数时，左半部分比右半部分多一个元素。由于左半部分所有元素都小于等于右半部分所有元素，排序后最中间的元素就是左半部分最大值。
算法返回 leftMax，因此奇数长度时结果正确。
结论 4：偶数长度时返回值正确
当总长度为偶数时，左右两部分元素个数相等。排序后中间两个元素分别是左半部分最大值和右半部分最小值。
算法返回它们的平均值，因此偶数长度时结果正确。
综上，算法能够正确返回两个正序数组的中位数。
示例分析
以 nums1 = [1,2]，nums2 = [3,4] 为例：
m = 2, n = 2
totalLeft = (2 + 2 + 1) / 2 = 2
合法分割为：
nums1 左侧：[1,2]
nums2 左侧：[]
nums1 右侧：[]
nums2 右侧：[3,4]
左半部分最大值是 2，右半部分最小值是 3。
总长度为偶数，因此中位数是：
(2 + 3) / 2 = 2.5
复杂度分析
- 时间复杂度：
O(log min(m, n))。算法只在较短数组上进行二分查找，满足题目要求的O(log (m + n))。 - 空间复杂度：
O(1)。只使用常数个变量。
边界情况
- 一个数组为空：分割全部落在另一个数组中，哨兵值可以统一处理。
- 两个数组长度和为奇数：返回左半部分最大值。
- 两个数组长度和为偶数：返回左右中间值的平均数。
- 所有较小元素都在同一个数组中：分割可能落在另一个数组的边界，哨兵值保证计算正确。