Very similar to the Matrix median problem. Some crazy corner cases though. Make sure you consider empty and singleton sets.

# Good problem, similar to Matrix median problem

can you explain how do we incorporate median for total number of elements as even, because in case of matrix median it was given that r*c is odd, how to we do it here?.

Let’s say total elements = 10(even).

Target = 10/2 = 5.

You binary search and find a number whose lower_bound gives 5 or >= 5 as value.

We’ve found one of our medians.

But this is an even case, we need to find one more to take average. Now repeat the same

process, but this time take target=6 instead of 5. It’ll work.

did you get right answer by doing it , i tried but coudnot solve because there was a case where elements were like 0 1 2 2 4 4 now i couldnot find second 2 by doing upper_bound

**parag_619**#5

Yes i get the right answer by doing this.

```
typedef long long ll;
ll cntBelow(const vector<int> &A, const vector<int> &B, ll mid) {
ll ind1 = upper_bound(A.begin(), A.end(), mid) - A.begin();
ll ind2 = upper_bound(B.begin(), B.end(), mid) - B.begin();
return (ind1 + ind2);
}
double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
ll n = A.size(), m = B.size();
if(n == 0) {
if(m%2 == 0) {
return (B[m/2 -1] + B[m/2])/2.0;
}
return B[m/2];
}
if(m == 0) {
if(n%2 == 0) {
return (A[n/2 -1] + A[n/2])/2.0;
}
return A[n/2];
}
ll num = (n+m)/2;
ll mini = (A[0] > B[0] ? B[0] : A[0]), maxi = (A[n-1] > B[m-1] ? A[n-1] : B[m-1]);
while(mini <= maxi) {
ll mid = (mini + maxi)/2;
ll cnt = cntBelow(A, B, mid);
if(cnt <= num) {
mini = mid+1;
}
else maxi = mid-1;
}
if((n+m)%2 != 0) return mini;
ll ans = mini;
mini = A[0] > B[0] ? B[0] : A[0];
maxi = A[n-1] > B[m-1] ? A[n-1] : B[m-1];
while(mini <= maxi) {
ll mid = (mini + maxi) /2;
ll cnt = cntBelow(A, B, mid);
if(cnt < num) {
mini = mid+1;
}
else maxi = mid-1;
}
return (ans + mini)/2.0;
}
```