# Solution in C++, well-explained

• ### Solution

Median is the middle number which partitions the sorted array into two halves with same length, even when it comes to two sorted array, the rule will always apply.

Overview of the partition:

``````  A[i-1]   |   A[i]
\|/
/|\
B[i-1]   |   B[j]
``````

So in this problem, we are to search out the four border numbers A[i-1] and A[i] in array-1 and B[j-1] and B[j] in array-2 to ensure that:

• First, `max(A[i-1],B[j-1])` is smaller than or equal to `min(A[i],B[j])`.
• Second, `len(A[0]...A[i-1])+len(B[0]...B[j-1])==len(A[i]...A[n-1])+len(B[j]...B[m-1])`, n and m is the size of the array-1 and array-2 respectively.
• Third, to ensure the above two conditions, there must be a equation `mid=i+j-1=(m+n-1)/2` and as a result A[i-1] corresponds to B[j] and B[j-1] corresponds to A[i]; so actually we need to search two pairs, which will meet the following requirements: `A[i-1]<=B[j]` and `B[j-1]<=A[i]`.

Now let's dive into details of its implementation.

• First, get the index of the final median index of the two arrays `mid=(m+n-1)/2=i+j-1`, in which case if the whole size of the two array is odd, then the median will be `max(A[i-1],B[j-1])`; if it's even, then the median will be `(max(A[i-1],B[j-1])+min(A[i],B[j]))/2`.
• Second, do the binary searching based on array-1, starting with `l=0`, `r=n-1` and `m1=l+((r-l)>>1)`; and the corresponding index in array-2 will be `m2=mid-m1`.
• Third, if `A[m1] < B[m2]` then we should select the bigger half by `l=m1+1` since `m1` is too small while we need to find the biggest `A[m1]` that is smaller than `B[m2]`, which can then ensure us `A[m1+1]>B[m2-1]`; otherwise select the smaller half by `r=m1-1` since it's too big, which can then ensure us `A[m1-1]<B[m2+1]`.
• Forth, after the searching, `r == l-1` and as a result `l` will point to `A[i]` while `r` pointing to `A[i-1]`, which means `A[i-1], A[i], B[j-1] and B[j]` are `A[r], A[l], B[mid-l] and B[mid-r]` respectively.
• Fifth, in the end, we can retrieve the median as `First` presents.
``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size() > nums2.size()) nums1.swap(nums2);
int size1 = nums1.size(), size2 = nums2.size(), size = size1+size2;
int mid = (size-1)/2, l = 0, r = size1-1;
while(l <= r){
int m1 = l+((r-l)>>1), m2 = mid-m1;
if(nums1[m1] > nums2[m2]) r = m1-1;
else l = m1+1;
}
int a = max(r>=0? nums1[r]:INT_MIN, mid-l>=0? nums2[mid-l]:INT_MIN);
if(size&1) return a;
int b = min(l<size1? nums1[l]:INT_MAX, mid-r<size2? nums2[mid-r]:INT_MAX);
return (a+b)/2.0;
}
};
``````

Always welcome new ideas and `practical` tricks, just leave them in the comments!

• Thanks for explanation. Typo in the diagram B[i-1] should be B[j-1]

• @tonytata Thank you so much, my careless. I've updated it now.

• This post is deleted!

• @LHearen int a = max(l>0? nums1[r]:INT_MIN, mid-l<nums2.size()? nums2[mid-l]:INT_MIN);
you can change it to
int a = max(l>0? nums1[r]:INT_MIN, nums2[mid-l]);
because mid-l<nums2.size() is absolutely true as l must large or equal than 0

• @508618087qq.com It's right about it, but it's related to many factors:

• `nums1.size() <= nums2.size()`
• `mid = (size-1)/2`
• `l>=0`

If one of the three conditions failed, then the result is not right. So it's not a good idea to remove the restraint. Maintenance and portability are also need to be considered here.

• `if(nums1.size() > nums2.size()) nums1.swap(nums2);`
As for the first `swapping` operation, we have to ensure the indexing of `m2` will always be valid.
the second array will encounter `out of range` error, but if we swap them, the `while` loop will handle this case automatically.