Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution 1 O($\log(m+n)$):

Note that we can check if an element A[i] is the median in constant time. Since the array is sorted A[i] is larger than i elements from array A, then if it is the median it needs to be larger than $\lfloor \frac{m+n}{2} \rfloor -i$ elements in array B. Hence to be the median i would mean that $B[j]\leq A[i]\leq B[j+1]$, where j=(m+n)/2-i-1. If it is not the median we can also know if A[i] is larger than the median, i.e. A[i]>B[j+1]. or smaller, i.e. A[i]<B[j]. Note that in the case of $m+n$ being even we have to obtain the previous element and return the average.

public class Solution {

  public double findMedianSortedArrays(int A[], int B[]) 

  {

     //Empty array cases

       if((A ==null || A.length==0) &&(B==null || B.length==0)) return 0.0;

     if(A==null || A.length==0) return B.length%2==1 ? B[B.length/2] :  (B[B.length/2]+B[B.length/2-1])/2.0;

     if(B==null || B.length==0) return A.length%2==1 ? A[A.length/2] :  (A[A.length/2]+A[A.length/2-1])/2.0;

     if(A.length>B.length) return findMedianSortedArrays(A, B, 0, A.length-1);

return findMedianSortedArrays(B, A, 0, B.length-1);

  }

  private double findMedianSortedArrays(int[] A, int[] B, int begin, int end) 

  {

if(begin>end) return findMedianSortedArrays(B, A, 0, B.length-1);

int i = (begin+end)/2;

int j = (A.length+B.length)/2-i-1;

if(j>=B.length || j>=0 && B[j]>A[i]) return findMedianSortedArrays(A, B, i+1, end); //A[i]>median

else if(j<-1 || j<B.length-1 && B[j+1]<A[i]) return findMedianSortedArrays(A, B, begin, i-1); //A[i]<median

if ((A.length+B.length)%2==1) //It is the median or the last element of the two that are needed

return A[i];

if(j>=0 && ( i==0 || B[j]>A[i-1]))

return (B[j]+A[i])/2.0;

return (A[i-1]+A[i])/2.0;

   }

}

Algorithm based on the idea given in [1]

Solution 2 O($\log^2(m+n)$):

Let's base our algorithm in binary search. If we select a candidate to be the median and we find the number of elements smaller than this element in the other array, we can shrink the arrays correspondingly.

public class Solution {
  public double findMedianSortedArrays(int A[], int B[]) 
  {
     if((A ==null || A.length==0) &&(B==null || B.length==0)) return 0.0;
     if(A==null || A.length==0) return B.length%2==1 ? B[B.length/2] :  (B[B.length/2]+B[B.length/2-1])/2.0;
     if(B==null || B.length==0) return A.length%2==1 ? A[A.length/2] :  (A[A.length/2]+A[A.length/2-1])/2.0;

     if(A.length>B.length)
return findMedianSortedArrays(A, B, 0, A.length-1, 0,B.length-1);
     return findMedianSortedArrays(B, A, 0, B.length-1, 0,A.length-1);
  }

  private double findMedianSortedArrays(int[] A, int[] B, int beginA, int endA, int beginB, int endB) 
  {
int pivot = A[(beginA+endA)/2];
int pos = binarySearch(B,beginB,endB+1,pivot);
int smallerThanPivot = (beginA+endA)/2 +pos;
if(smallerThanPivot<(A.length+B.length-1)/2)
{
   beginA=(beginA+endA)/2+1;
   beginB=pos;
      if(endA-beginA>endB-beginB) 
                return findMedianSortedArrays(A, B, beginA, endA, beginB,endB);
   else 
                return findMedianSortedArrays(B, A, beginB, endB, beginA,endA);
}
if(smallerThanPivot>(A.length+B.length-1)/2)
{
   endA=(beginA+endA)/2-1;
   endB=pos-1;
   if(endA-beginA>endB-beginB)
                return findMedianSortedArrays(A, B, beginA, endA, beginB,endB);
   else 
                return findMedianSortedArrays(B, A, beginB, endB, beginA,endA);
}
if ((A.length+B.length)%2==1)
    return pivot;
int next = (beginA+endA)/2+1<A.length ? A[(beginA+endA)/2+1] : Integer.MAX_VALUE;
next = pos<B.length && B[pos]<next ? B[pos] : next;
return (pivot+next)/2.0;
   }

   private int binarySearch(int[] A, int begin, int end, int value)
   {
        //We assure that A[0..begin-1]<=value<=A[end+1...]
if(begin>=end)
   return begin;
int midpoint=(begin+end)/2;
if (A[midpoint]==value) return midpoint;
else if (A[midpoint]<value) return binarySearch(A, midpoint+1, end, value);
else return binarySearch(A, begin, midpoint, value);
   }
}

[1] E. D. Demaine, C. E. Leiserson, "Introduction to Algorithms. Problem Set 9 Solutions " Available at: http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf