基于二分查找的两个有序数组中位数求解逻辑错误排查

我们先看你的测试用例：

• A = {-50,-41,-40,-19,5,21,28}（长度7）
• B = {-50,-21,-10}（长度3）
  总长度10（偶数），合并后数组为{-50,-50,-41,-40,-21,-19,-10,5,21,28}，中位数是第5和第6小元素的平均值：(-21 + (-19))/2 = -20。但你的代码最终得到的lo是-20，计算出的中位数是(-20 + (-19))/2 = -19.5，明显错误。下面是具体的错误分析：

1. 二分查找的核心逻辑错误 #

你的代码目标是找到最大的mid，使得**<=mid的元素总数t <= k**（其中k=(n+m+1)/2=5），但这个逻辑是错误的。我们需要找的是第k小的元素，也就是满足<=mid的元素总数t >=k的最小mid——因为第k小元素是第一个能让t达到k的数值。

你的代码在t<=k时会将lo=mid，这会导致搜索空间向右偏移：

• 当mid=-21时，t=5（刚好等于k），你的代码将lo设为-21；
• 后续迭代中，mid=-16时t=6>5，hi=-17；mid=-19时t=6>5，hi=-20；mid=-20时t=5<=5，lo=-20；
• 最终lo停在-20，但-20并不是第5小的元素（第5小是-21）。

正确的二分逻辑应该是：

• 如果t <k：说明当前mid太小，需要向右找，lo=mid+1；
• 如果t >=k：说明当前mid可能是候选，或需要向左找更小的候选，hi=mid；
• 同时mid的计算要改为向下取整（mid=lo+(hi-lo)/2），避免死循环。

2. 下一个元素查找时的数组越界问题 #

在偶数长度的分支中，你直接访问A[ind1]和B[ind2]，但没有考虑ind1 >=n或ind2 >=m的情况：

• 当lo是数组中的最大值时，upper_bound会返回数组末尾，此时ind1=n或ind2=m，访问对应索引会导致越界，触发未定义行为。

修正后的代码 #

#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    int n = A.size();
    int m = B.size();
    
    // 处理空数组情况
    if (n == 0) {
        if (m % 2 == 0) {
            return (B[m/2] + B[m/2-1]) / 2.0;
        } else {
            return B[m/2];
        }
    }
    if (m == 0) {
        if (n % 2 == 0) {
            return (A[n/2] + A[n/2-1]) / 2.0;
        } else {
            return A[n/2];
        }
    }
    
    int lo = min(A[0], B[0]);
    int hi = max(A.back(), B.back());
    int k = (n + m + 1) / 2; // 第k小元素
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2; // 向下取整
        int t = upper_bound(A.begin(), A.end(), mid) - A.begin();
        t += upper_bound(B.begin(), B.end(), mid) - B.begin();
        
        if (t < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    // lo就是第k小元素
    if ((n + m) % 2 == 1) {
        return lo;
    } else {
        // 找下一个元素，处理越界情况
        int ind1 = upper_bound(A.begin(), A.end(), lo) - A.begin();
        int ind2 = upper_bound(B.begin(), B.end(), lo) - B.begin();
        double next;
        
        if (ind1 >= n) {
            next = B[ind2];
        } else if (ind2 >= m) {
            next = A[ind1];
        } else {
            next = min(A[ind1], B[ind2]);
        }
        
        return (lo + next) / 2.0;
    }
}

修正后的代码验证 #

针对你的测试用例：

• 二分过程最终会找到lo=-21（第5小元素）；
• 找下一个元素时，ind1=3（A[3]=-19），ind2=2（B[2]=-10），next=-19；
• 中位数为(-21 + (-19))/2 = -20，与预期一致。

内容的提问来源于stack exchange，提问作者Arun R Nambiar