LeetCode 4困难二分查找
寻找两个正序数组的中位数 图解题解
两个有序数组找中位数，不用合并——在短数组上二分「切一刀」，O(log min(m,n)) 直接定位。
找两个有序书架合并后的中间那本，不用真的把两排书全搬到一起再数。只在短书架上「切一刀」：左边凑够合并总数的一半，另一刀位置由此反推；再验一个条件——左半最大值都不超过右半最小值。条件不满足就朝违规方向挪切点，满足就直接从四个边界值里算出中位数，全程只在短数组上二分。
这道题到底在问什么
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。
- nums1, nums2
- [1,2], [3,4,5,6]
- 输出
- 3.5
最优解：一步一步想明白
⚠️ 容易写错的地方
✗ 错：在长数组二分
✓ 对：确保 nums1 更短
切分点边界更好处理
✗ 错：奇偶长度统一错误
✓ 对：奇数取左半最大，偶数取两侧平均
中位数定义不同
完整代码（Python / C++ / Java）
Python
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m = len(nums1)
n = len(nums2)
half = (m + n + 1) // 2
l = 0
r = m
while l <= r:
i = (l + r) // 2
j = half - i
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
if (m + n) % 2:
return max(left1, left2)
return (max(left1, left2) + min(right1, right2)) / 2
if left1 > right2:
r = i - 1
else:
l = i + 1C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
if (a.size() > b.size()) swap(a, b);
int m = a.size(), n = b.size(), half = (m + n + 1) / 2;
int l = 0, r = m;
while (l <= r) {
int i = (l + r) / 2, j = half - i;
long L1 = i > 0 ? a[i-1] : LONG_MIN, R1 = i < m ? a[i] : LONG_MAX;
long L2 = j > 0 ? b[j-1] : LONG_MIN, R2 = j < n ? b[j] : LONG_MAX;
if (L1 <= R2 && L2 <= R1) {
if ((m + n) % 2) return max(L1, L2);
return (max(L1, L2) + min(R1, R2)) / 2.0;
}
if (L1 > R2) r = i - 1; else l = i + 1;
}
return 0.0;
}
};Java
class Solution {
public double findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) { int[] tmp = a; a = b; b = tmp; }
int m = a.length, n = b.length, half = (m + n + 1) / 2;
int l = 0, r = m;
while (l <= r) {
int i = (l + r) / 2, j = half - i;
long L1 = i > 0 ? a[i-1] : Long.MIN_VALUE, R1 = i < m ? a[i] : Long.MAX_VALUE;
long L2 = j > 0 ? b[j-1] : Long.MIN_VALUE, R2 = j < n ? b[j] : Long.MAX_VALUE;
if (L1 <= R2 && L2 <= R1) {
if ((m + n) % 2 == 1) return Math.max(L1, L2);
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
}
if (L1 > R2) r = i - 1; else l = i + 1;
}
return 0.0;
}
}复杂度
时间复杂度
O(log min(m,n))
只在短数组二分
空间复杂度
O(1)
只用边界变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 寻找两个正序数组的中位数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么在「较短」数组上二分？+
切点范围 0..短数组长，二分次数 O(log min(m,n)) 更少，且另一刀 j 不会越界。
总长奇偶怎么取中位数？+
奇数取左半最大；偶数取(左半最大+右半最小)/2。左半固定为 (m+n+1)/2 保证奇数时多一个在左。
切到数组头/尾的边界怎么处理？+
切点在端点时，用 ±∞ 兜住越界的 nums1[i-1] 或 nums2[j]，让交叉条件恒成立、不用特判。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。