## Wednesday, March 20, 2013

### 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)).

For any value in loc i in array A, it takes only O(1) time to determine whether it is the median: only need to check whether there are exact amount of numbers in array B that are less than the value.

class Solution {
int[] A;
int[] B;

double median(int A[]){
if(A.length % 2 == 0)
return 0.5 * (A[A.length/2 -1] + A[A.length/2]);
else
return A[A.length/2];
}

double med(int small, int large){
if((A.length + B.length) % 2 == 0)
return 0.5*(double)(small + large);
else return Math.max(small,large);
}

double find(int A[], int B[], int left,int right){

if(left > right) return find(B,A,0,B.length-1);
int mid = left + (right-left+1)/2;
int r1 = mid + 1;
int r2 = (A.length + B.length)/2 - r1;

if(r2 > B.length) return find(A,B,mid+1,right);
else if (r2 < 0) return find(A,B,left,mid-1);
else if (r2 == 0){
if(A[mid] <= B[0]) {
int min = B[0];
if(mid+1<A.length) if(min > A[mid+1]) min = A[mid+1];
return med(A[mid],min);
}
else return find(A,B,left,mid-1);
}

if(B[r2-1] <= A[mid]){
if(r2 > B.length-1){
return med(A[mid],A[mid+1]);
}
else if(B[r2] >= A[mid]){
int min = 0;
if(mid+1>A.length-1){
min = B[r2];
}
else{
min = Math.min(A[mid+1],B[r2]);
}
return med(A[mid],min);

}
else {
return find(A,B,left,mid-1);
}
}
else{
return find(A,B,mid+1,right);
}

}

public double findMedianSortedArrays(int A[], int B[]) {
// Start typing your Java solution below
// DO NOT write main() function
this.A = A; this.B=B;
if(B.length == 0){
return median(A);
}
else if(A.length == 0) return median(B);

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