为了方便描述，不妨假设最终分割后，数组 nums1 左侧部分是 A，数组 nums2 左侧部分是 B。由于题中给出的数组都是排好序的，在排好序的数组中查找很容易想到可以用二分查找（Binary Search)·, 这里对数组长度小的做二分以减少时间复杂度。对较小的数组做二分可行的原因在于如果一个数组的索引 i 确定了，那么另一个数组的索引位置 j 也是确定的，因为 (i+1) + (j+1) 等于 (m + n + 1) / 2，其中 m 是数组 A 的长度， n 是数组 B 的长度。具体来说，我们可以保证数组 A 和 数组 B 做 partition 之后，len(Aleft)+len(Bleft)=(m+n+1)/2
接下来需要特别注意四个指针：leftp1, rightp1, leftp2, rightp2，分别表示 A 数组分割点，A 数组分割点右侧数，B 数组分割点，B 数组分割点右侧数。不过这里有两个临界点需要特殊处理：
如果分割点左侧没有数，即分割点索引是 0，那么其左侧应该设置为无限小。
如果分割点右侧没有数，即分割点索引是数组长度-1，那么其左侧应该设置为无限大。
如果我们二分之后满足：leftp1 < rightp2 and leftp2 < rightp1,那么说明分割是正确的，直接返回max(leftp1, leftp2)+min(rightp1, rightp2) 即可。否则，说明分割无效，我们需要调整分割点。
/**
* 二分解法
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
// make sure to do binary search for shorten array
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
let low = 0;
let high = m;
while (low <= high) {
const i = low + Math.floor((high - low) / 2);
const j = Math.floor((m + n + 1) / 2) - i;
const maxLeftA = i === 0 ? -Infinity : nums1[i - 1];
const minRightA = i === m ? Infinity : nums1[i];
const maxLeftB = j === 0 ? -Infinity : nums2[j - 1];
const minRightB = j === n ? Infinity : nums2[j];
if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
return (m + n) % 2 === 1
? Math.max(maxLeftA, maxLeftB)
: (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
} else if (maxLeftA > minRightB) {
high = i - 1;
} else {
low = low + 1;
}
}
};
Java Code:
class MedianSortedTwoArrayBinarySearch {
public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
// do binary search for shorter length array, make sure time complexity log(min(m,n)).
if (nums1.length > nums2.length) {
return findMedianSortedArraysBinarySearch(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int lo = 0;
int hi = m;
while (lo <= hi) {
// partition A position i
int i = lo + (hi - lo) / 2;
// partition B position j
int j = (m + n + 1) / 2 - i;
int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int minRightA = i == m ? Integer.MAX_VALUE : nums1[i];
int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int minRightB = j == n ? Integer.MAX_VALUE : nums2[j];
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
// total length is even
if ((m + n) % 2 == 0) {
return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
} else {
// total length is odd
return (double) Math.max(maxLeftA, maxLeftB);
}
} else if (maxLeftA > minRightB) {
// binary search left half
hi = i - 1;
} else {
// binary search right half
lo = i + 1;
}
}
return 0.0;
}
}
CPP Code:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) swap(nums1, nums2);
int M = nums1.size(), N = nums2.size(), L = 0, R = M, K = (M + N + 1) / 2;
while (true) {
int i = (L + R) / 2, j = K - i;
if (i < M && nums2[j - 1] > nums1[i]) L = i + 1;
else if (i > L && nums1[i - 1] > nums2[j]) R = i - 1;
else {
int maxLeft = max(i ? nums1[i - 1] : INT_MIN, j ? nums2[j - 1] : INT_MIN);
if ((M + N) % 2) return maxLeft;
int minRight = min(i == M ? INT_MAX : nums1[i], j == N ? INT_MAX : nums2[j]);
return (maxLeft + minRight) / 2.0;
}
}
}
};
Python3 Code:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
N = len(nums1)
M = len(nums2)
if N > M:
return self.findMedianSortedArrays(nums2, nums1)
lo = 0
hi = N
combined = N + M
while lo <= hi:
mid1 = lo + hi >> 1
mid2 = ((combined + 1) >> 1) - mid1
leftp1 = -float("inf") if mid1 == 0 else nums1[mid1 - 1]
rightp1 = float("inf") if mid1 == N else nums1[mid1]
leftp2 = -float("inf") if mid2 == 0 else nums2[mid2 - 1]
rightp2 = float("inf") if mid2 == M else nums2[mid2]
# Check if the partition is valid for the case of
if leftp1 <= rightp2 and leftp2 <= rightp1:
if combined % 2 == 0:
return (max(leftp1, leftp2)+min(rightp1, rightp2)) / 2.0
return max(leftp1, leftp2)
else:
if leftp1 > rightp2:
hi = mid1 - 1
else:
lo = mid1 + 1
return -1
复杂度分析
时间复杂度：$O(log(min(m, n)))$
空间复杂度：$O(log(min(m, n)))$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
