Java两个有序数组的中位数

题目描述：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2，请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题思路：

1. 将两个数组合并成一个数组，再对合并后的数组进行排序，找到中位数

时间复杂度为O(m+n)log(m+n)，不符合题目要求

2. 利用二分法查找

首先，我们可以理解中位数的定义：如果某个有序数组的长度是奇数，那么其中位数就是最中间那个元素，如果是偶数，那么就是最中间两个元素的平均值。

在本题中，我们需要找到两个有序数组 A 和 B 的中位数，我们可以考虑从中位数的定义入手。如果我们能够将两个数组分别分成两部分，并且使得左半部分和右半部分分别满足以下两个条件：

1.左半部分的所有元素都小于右半部分的所有元素。

2.左半部分和右半部分分别包含了 A 和 B 数组的一半元素。

那么中位数就可以通过以下公式得到：

median = max(left_part) (len(A) + len(B) 为偶数)
median = (max(left_part) + min(right_part))/2 (len(A) + len(B) 为奇数)

为了使得划分满足上述两个条件，我们可以对较短的那个数组进行二分查找，然后根据查找到的位置将两个数组进行划分，最后再根据上述公式计算中位数。

具体实现见代码。

Java代码：

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

//确保nums1比nums2短
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}

int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (i < iMax && nums2[j - 1] > nums1[i]) {
iMin = i + 1;
} else if (i > iMin && nums1[i - 1] > nums2[j]) {
iMax = i - 1;
} else {
int maxLeft = 0;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}

if ((m + n) % 2 == 1) {
return maxLeft;
}

int minRight = 0;
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = Math.min(nums1[i], nums2[j]);
}

return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}