Median of two sorted array using Binary Search theorem

Question

The problem is to find median of two sorted array that may/may not have different sized array.

The approach used is binary search with search space [ lowest element , highest element ].Search space is reduced based on number of elements less than median must be less than or equal to (n+m+1)/2.n and being size of two array respectively. In case of even number of elements average is taken with next element. The code is as follows.

  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;
    
}

The code gives wrong output is the below test case: A = {-50,-41,-40,-19,5,21,28} B = {-50,-21,-10} The dry run helped me understand where it goes wrong but I am not able to figure out what is the logical error in the above approach.

Answer 1

There are two logical errors in above code:

1. We want to find first elem where count is equal to (n+m+1)/2. But the given code finds first elem where condition is false.So update logic should be :

      if(t < ((n+m+1)/2) ) {
          lo = mid+1;
      }else{
          hi = mid;
      }
   

   This link Top Coder Binary Search have good explanation of above two scenarios.

2. When total elements is even, finding next elem to compute average needs to handle two corner cases.

   a. When the element has duplicate values. b. Both expected elements is present in one array.

   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;