LeetCode 第 4 题要求在两个正序数组中找出中位数，时间复杂度 O(log(m+n))。这题主要考察对中位数本质和二分查找的理解。下面先梳理核心思路，再给出五种实现，最后分析不同场景怎么选。
问题
输入两个升序数组 nums1 和 nums2（大小分别为 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
约束：0 <= m,n <= 1000，1 <= m+n <= 2000，元素范围 [-10⁶, 10⁶]。
核心思路
中位数可以转化为第 k 小问题。设总长度 L = m+n，则：
- 奇数时，中位数是第
(L+1)/2小的数。 - 偶数时，中位数是第
L/2小和第L/2+1小的平均值。
于是只要能在 O(log(m+n)) 内找到第 k 小元素就能求解。数组有序→二分，每次排除一部分不可能的元素。主要有两类写法：基于分割点的二分（标准做法）和递归/迭代地'砍掉' k/2 个元素。
另外注意，为了二分范围尽可能小，一般让 nums1 作为较短数组。
解法一：二分分割（标准）
思路：将两个数组分成左右两部分，使得左半部分共 (L+1)/2 个元素，且左边最大值 ≤ 右边最小值。分割点 i 在 nums1 上二分，j 由 j = leftCount - i 确定。检查条件 nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。满足条件后根据总长度奇偶取最大值或平均值。
实现如下：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
nums1.length;
nums2.length;
m + n;
(total + ) / ;
, right = m;
(left <= right) {
left + (right - left) / ;
leftCount - i;
(i == ) ? Integer.MIN_VALUE : nums1[i - ];
(i == m) ? Integer.MAX_VALUE : nums1[i];
(j == ) ? Integer.MIN_VALUE : nums2[j - ];
(j == n) ? Integer.MAX_VALUE : nums2[j];
(nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
(total % == ) {
Math.max(nums1LeftMax, nums2LeftMax);
} {
Math.max(nums1LeftMax, nums2LeftMax);
Math.min(nums1RightMin, nums2RightMin);
(leftMax + rightMin) / ;
}
} (nums1LeftMax > nums2RightMin) {
right = i - ;
} {
left = i + ;
}
}
;
}
}
