使用二进制搜索定理的两个排序数组的中位数

Question

问题是找到 may/may 没有不同大小数组的两个排序数组的中位数。

使用的方法是二分查找space [最低元素，最高元素]。搜索space根据小于中位数的元素数减少，必须小于或等于（ n+m+1)/2.n 分别是两个数组的大小。如果元素数量为偶数，则取下一个元素的平均值。代码如下

  int  n =A.size();
  int  m = B.size();
  if(n < 1){
     if(m%2==0){
        return (B[m/2] + B[m/2-1])/2;
     }else{
        return B[m/2];
     }
 }else if(m < 1){
     if(n%2==0){
        return (A[n/2] + A[n/2-1])/2;
     }else{
        return A[n/2];
     }
 }
int lo = (A[0] < B[0] )? A[0] : B[0];
int hi = (A[n-1] > B[m-1] )? A[n-1] : B[m-1];
while(lo < hi){
    int mid = lo + ( hi - lo+1)/2;
    int t = 0;
    t += upper_bound(A.begin() A.end() mid) - A.begin();
    t += upper_bound(B.begin() B.end() mid) - B.begin();
    if(t > ((n+m+1)/2) ) {
        hi = mid-1;
    }else{
        lo = mid;
    }
    
}
if(  ((n+m)%2))
    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 nxt = ( A[ind1] < B[ind2] )? A[ind1] : B[ind2];
    double x = lo;
    return (x+nxt)/2;
    
}

代码给出错误的输出是下面的测试用例： A = {-50,-41,-40,-19,5,21,28} B = {-50,-21,-10} 干运行帮助我理解了哪里出了问题，但我无法弄清楚上述方法中的逻辑错误是什么。

Answer 1

以上代码有两个逻辑错误：

我们想要找到计数等于 (n+m+1)/2 的第一个元素。但是给定的代码找到条件为 false.So 的第一个 elem 更新逻辑应该是：
```
   if(t < ((n+m+1)/2) ) {
       lo = mid+1;
   }else{
       hi = mid;
   }
```
这篇linkTop Coder Binary Search很好的解释了以上两种情况

当元素总数为偶数时，找到下一个元素来计算平均值需要处理两个极端情况。

一个。当元素有重复值时。 b.两个预期元素都存在于一个数组中。

if(((n+m)%2))
   return lo;
else{


   int ind1 = lower_bound(A.begin(), A.end(), lo) - A.begin();
   int ind2 = lower_bound(B.begin(), B.end() ,lo) - B.begin();
   double nxt = 0.0;
   //check for duplicates
   if(A[ind1]==lo){
          if(ind2 < B.size())  // check for both elements in same array
               nxt  = ( A[ind1+1] < B[ind2] )? A[ind1+1] : B[ind2];
          else 
               nxt = A[ind1+1];
   }else{
          if(ind1 < A.size())
               nxt = ( A[ind1] < B[ind2+1] )? A[ind1] : B[ind2+1];
          else
               nxt = B[ind2+1];
   }
   double x = lo;
   return (x+nxt)/2;

使用二进制搜索定理的两个排序数组的中位数

Median of two sorted array using Binary Search theorem

arrays

sorting

algorithm

binary-search