Question

There are two sorted arrays nums1 and nums2 both of size n. Find the median of the two sorted arrays. The overall run time complexity should be O(log(n)).

Answer 1

You can convert this problem to the problem of finding kth element, k is (A's length + B' Length)/2.
If any of the two arrays is empty, then the kth element is the non-empty array's kth element. If k == 0, the kth element is the first element of A or B.

For normal cases(all other cases), we need to move the pointer at the pace of half of the array size to get O(log(n)) time.

public double getSortedArraysMedian(int[] numbers1, int[] numbers2) {
int total = numbers1.length+numbers2.length;
if(total%2==0){
return (getKthElement(numbers1, 0, numbers1.length-1, numbers2, 0, numbers2.length-1, total/2)
+ getKthElement(numbers1, 0, numbers1.length-1, numbers2, 0, numbers2.length-1, total/2-1))/2.0;
}else{
return getKthElement(numbers1,0, numbers1.length-1, numbers2, 0, numbers2.length-1, total/2);
}
}

//k is the index starting from 0
private int getKthElement(int[] numbers1, int i1, int j1, int[] numbers2, int i2, int j2, int k){
if(j1<i1){
return numbers2[i2+k];
}
if(j2<i2){
return numbers1[i1+k];
}

if(k==0){
return Math.min(numbers1[i1], numbers2[i2]);
}

int len1 = j1 - i1 + 1;
int len2 = j2 - i2 + 1;

int m1 = k*len1/(len1+len2);
int m2 = k - m1 - 1;

m1 += i1;
m2 += i2;

if(numbers1[m1]<numbers2[m2]){
k = k-(m1-i1+1);
j2 = m2;
i1 = m1+1;
}else{
k = k-(m2-i2+1);
j1 = m1;
i2 = m2+1;
}

return getKthElement(numbers1, i1, j1, numbers2, i2, j2, k);
}