# Share my O(log(m+n)) code with some thought about it

• Like many other one's code, the main difficulty is to find the kth smallest element from two sorted arrays with time complexity O(log(m+n)). Why this is possible is that this algorithm jumps the ones which CANNOT be the kth smallest element.

Here I give some examples showing how to understand this algorithm,

1. We want to rule out the 1,2,...,k-1th smallest elements of both arrays.

2. If k = 10, then k is larger than 9 elements, we can have that either array1[0] or array2[0] is one of those 9 elements. (Otherwise, array1[0] and array2[0] are larger than this kth elements which leads to a contradiction)

3. Through (2), if we want to rule out the 1,2,...,k-1 smallest elements, we can have conclusion that, either array1[k/2-1] or array2[k/2-1] is one of those k-1 elements. WLOG, say it's array1[k/2-1], elements from 0 to k/2-1 of array1 can be ignore.

4. From (3), we have shrink the problem size. We can use recursion to solve the smaller problem.

The Java code is following,

``````public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if((nums1.length + nums2.length) % 2 == 0){
double d1 = getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2);
double d2 = getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2+1);
return (d1+d2)/2;
}else{
return getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2+1);
}
}
private double getkth(int[] n, int ni, int[] m, int mi, int k){
if(ni == n.length)
return m[mi+k-1];
if(mi == m.length)
return n[ni+k-1];
if(k == 1)
return  (n[ni] < m[mi]) ? n[ni] : m[mi];

int i = (k/2+ni > n.length) ? n.length : k/2+ni;
int j = (k/2+mi > m.length) ? m.length : k/2+mi;
if(n[i-1] < m[j-1])
return getkth(n, i, m, mi, k-(i-ni));
else
return getkth(n, ni, m, j, k-(j-mi));
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.