直接归并需遍历全部元素，时间复杂度为O(m+n)；而二分法将中位数问题转化为“找第k小元素”，每次淘汰k/2个不可能候选，通过偏移量递归实现O(log(m+n))。
为什么直接归并做不到 O(log(m+n))
归并两个升序数组再取中位数，本质是遍历全部元素，时间复杂度固定是 O(m + n)。二分法能降复杂度，关键不是在数组上“二分下标”，而是把「找第 k 小元素」作为子问题，每次淘汰 k/2 个不可能包含答案的候选——这才是 O(log(m + n)) 的来源。
核心思路：把中位数转成「找第 k 小」问题
设总长度为 len = m + n，中位数就是第 (len + 1) / 2 小（奇数）或第 len / 2 和 len / 2 + 1 小的平均值（偶数）。所以只需实现一个高效找第 k 小的函数 findKthElement。
该函数每次比较 nums1[k/2 - 1] 和 nums2[k/2 - 1]（注意下标越界要处理），较小者所在数组的前 k/2 个元素全可排除——因为它们都比这个较小值小，而我们要的是第 k 小，不可能落在这些位置里。
- 若
nums1越界或nums1[k/2 - 1] > nums2[k/2 - 1]，则丢弃nums2前k/2个 - 否则丢弃
nums1前k/2个 - k 更新为
k - k/2，递归继续 - 边界：k == 1 时直接返回两数组首元素较小值；某数组空时直接取另一数组第 k 个
容易踩的坑：索引计算和越界判断
常见错误是用 k/2 当作数组下标直接访问，但实际要取 min(k/2, size) 防越界；更关键的是，每次递归传入的起始位置不是从 0 开始，必须用偏移量（如 start1, start2）维护，而不是拷贝子数组——否则空间变 O(m + n)，且失去对数时间保障。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
例如，当 nums1 剩余长度不足 k/2，应拿 nums1 最后一个元素和 nums2[start2 + k/2 - 1] 比，然后直接排除整个 nums1 剩余部分（共 nums1.size() - start1 个），k 减去这个数量。
C++ 实现关键片段（不带完整类封装）
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if (len % 2 == 1) {
return findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
} else {
int a = findKthElement(nums1, 0, nums2, 0, len / 2);
int b = findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
return (a + b) / 2.0;
}
}
<p>int findKthElement(const vector<int>& nums1, int start1,
const vector<int>& nums2, int start2, int k) {
if (start1 >= nums1.size()) return nums2[start2 + k - 1];
if (start2 >= nums2.size()) return nums1[start1 + k - 1];
if (k == 1) return min(nums1[start1], nums2[start2]);</p><pre class="brush:php;toolbar:false;">int mid1 = start1 + k / 2 - 1;
int mid2 = start2 + k / 2 - 1;
int key1 = (mid1 < nums1.size()) ? nums1[mid1] : INT_MAX;
int key2 = (mid2 < nums2.size()) ? nums2[mid2] : INT_MAX;
if (key1 < key2) {
return findKthElement(nums1, mid1 + 1, nums2, start2, k - k / 2);
} else {
return findKthElement(nums1, start1, nums2, mid2 + 1, k - k / 2);
}}
注意 INT_MAX 是占位符，不是真实数组值；mid1 + 1 是新起点，不是跳过一个元素那么简单——它代表已排除 mid1 - start1 + 1 个元素，这个数量必须严格等于 k/2 或实际可用长度。
真正难的不是写对逻辑，而是验证所有边界组合：一空、二空、k=1、k=2、某数组只剩 1 个元素却要取 k=3……这些 case 不手工列几组输入跑一遍，很容易漏判。
