Median of two Sorted Arrays

Median of two Sorted Arrays

20%

Accepted

There are two sorted arrays A andB of size m and n respectively. Find the median of the two sorted arrays.

Have you met this question in a real interview? 

Yes

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should beO(log (m+n)).

class Solution {

    /**

     * @param A: An integer array.

     * @param B: An integer array.

     * @return: a double whose format is *.5 or *.0

     */

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

       // write your code here

  int m = A.length, n = B.length;

  if((m + n) % 2 == 1){

 return  _findMedian(A, B, 0, m - 1, 0, n-1, (m+n)/2);

  } else {

  return (_findMedian(A, B, 0, m - 1, 0, n-1, (m+n)/2) + _findMedian(A, B, 0, m - 1, 0, n-1, (m+n)/2 - 1)) * 0.5;

  }

       

   }

   

   private int _findMedian(int[] A, int[] B, int aStart, int aEnd,  int bStart, int bEnd, int k){

  int aLen = aEnd - aStart + 1;

  int bLen = bEnd - bStart + 1;

  if(aLen == 0) return B[bStart+k];

  if(bLen == 0) return A[aStart+k];

  if(k == 0) return A[aStart] > B[bStart] ? B[bStart] : A[aStart];

  int aMid = k*aLen/(aLen+bLen); // mid index = k + start(merged two list);

  int bMid = k - aMid - 1;

  aMid = aStart + aMid;

  bMid = bStart + bMid;

  if(A[aMid] > B[bMid]){

      k = k - (bMid - bStart + 1);

  aEnd = aMid;

  bStart = bMid + 1;

  

  } else {

       k = k - (aMid - aStart + 1);

  aStart = aMid + 1;

  bEnd = bMid;

 

  }

  return _findMedian(A, B, aStart, aEnd, bStart, bEnd, k);

   }

}