# Share my simple O(log(m+n)) solution for your reference

• Binary search. Call 2 times getkth and k is about half of (m + n). Every time call getkth can reduce the scale k to its half. So the time complexity is log(m + n).

``````class Solution {
public:
int getkth(int s[], int m, int l[], int n, int k){
// let m <= n
if (m > n)
return getkth(l, n, s, m, k);
if (m == 0)
return l[k - 1];
if (k == 1)
return min(s[0], l[0]);

int i = min(m, k / 2), j = min(n, k / 2);
if (s[i - 1] > l[j - 1])
return getkth(s, m, l + j, n - j, k - j);
else
return getkth(s + i, m - i, l, n, k - i);
return 0;
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
int l = (m + n + 1) >> 1;
int r = (m + n + 2) >> 1;
return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
}
};``````

• could you explain int l = (m + n + 1) >> 1; int r = (m + n + 2) >> 1; ?

• get the medians. l and r are the medians.
when n + m is even, l + 1 == r
when n + m is odd, l == r
we can merge 2 cases

• How can OJ accept it? for line return getkth(s, m, l + j, n - j, k - j);
l is an array, while j is an integer, it can't compile.

• `l + j` means `l[j]`. Have you ever submitted this code? I did it. It is accepted.

• here l + j meas the address of l[j]

• I didn't submitted in OJ, but got compile error in local machine.

• Can you explain when "return 0" will be reached, or why we need "return 0" here? Plus, we may need cover the case when both arrays are empty

• it's my test code. I forget to delete it. Ignore this line.

• so when l == r, you will run it twice.

• it does not reduce the scale k to its half. in fact, k will be its 3/4 every time.

• u r right. For readable and my laziness, i don't add this opt.:-)

• This codes are great.

if (m > n)
return getkth(l, n, s, m, k);

• I think j = min(n, k / 2) is not necessary. Because if k/2 > n then we must have k/2 > m also, since m <= n.

Then in this case we cannot have the expected value since m+n < k. According to this algorithm it should not happen.

And I change it to just j = k/2 the solution also accepted.

• Yes, I agree with you!

• Hi vaputa,

Thanks for your sharing! I might have further improved your solution to O(log(min(m,n)). Could you help to confirm the correctness of the complexity?

``````class Solution {
private:
int getkth_(int nums1[], int len1, int nums2[], int len2, int k){
if (len1 > len2)
return getkth_(nums2, len2, nums1, len1, k);
if(len1 == 0)
return nums2[k-1];
if(k==1)
return min(nums1[0], nums2[0]);
int i = (len1+1)/2, j = k - i;
if(nums1[i-1] < nums2[j-1])
return getkth_(nums1+i, len1-i, nums2, j, k-i);
else
return getkth_(nums1, i, nums2+j, len2-j, k-j);
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
int k = (len1 + len2 + 1) >> 1;
if((len1 + len2) & 1)
return getkth_(&nums1[0], len1 ,&nums2[0], len2, k);
else {
return (getkth_(&nums1[0], len1 ,&nums2[0], len2, k) + getkth_(&nums1[0], len1 ,&nums2[0], len2, k+1)) / 2.0;
}
}
};``````

• I have got the same idea too.

however, there is a large chance that this code is wrong.

``````   if(nums1[i-1] < nums2[j-1])
return getkth_(nums1+i, len1-i, nums2, j, k-i);
else
return getkth_(nums1, i, nums2+j, len2-j, k-j);
``````

what if nums1[i-1]==nums2[j-1] ?
it seems when this happen, you can do nothing with a step of K（but it's ok with a step of k/2).

haven't figured out yet....

• I think your concern doesn't exist. The condition of "nums1[i-1]==nums2[j-1]" can be merged into both ">" and "<". I merged it into ">" in above snippet. Because we can guarantee that if they are equal, at least one of them is not the median we want.

• This is what I think can be rather easier to implement in real time, with findKth, if you know findKth

Awesome

• I think :
return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
can make better to
if(l == r) return getKth(A, size1 ,B, size2, l);
return (getkth(A, size1 ,B, size2, l) + getkth(A, size1, B, size2, r)) / 2.0;

So when (m+n) is odd, it only calls getkth() once.

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