I revised the code from @shichaotan for recent cpp code.

I will explain the algo. after the code.

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
int k = (len1 + len2 + 1) / 2; // for odd total it is the mid one, for even it is the left mid
int num1 = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k);
if ((len1 + len2) & 1) return num1; // the sum of lengths is odd
int num2 = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k + 1);
return (num1 + num2) / 2.0;
}
private:
int findKth(vector<int>& nums1, int L1, int R1, vector<int>& nums2, int L2, int R2, int k) {
if (L1 > R1) return nums2[L2 + k - 1];
if (L2 > R2) return nums1[L1 + k - 1];
int mid1 = L1 + (R1 - L1) / 2, mid2 = L2 + (R2 - L2);
if (nums1[mid1] <= nums2[mid2]) {
if (k <= (mid1 - L1) + (mid2 - L2) + 1) return findKth(nums1, L1, R1, nums2, L2, mid2 - 1, k);
else return findKth(nums1, mid1 + 1, R1, nums2, L2, R2, k - (mid1 - L1) - 1);
} else {
if (k <= (mid1 - L1) + (mid2 - L2) + 1) return findKth(nums1, L1, mid1 - 1, nums2, L2, R2, k);
else return findKth(nums1, L1, R1, nums2, mid2 + 1, R2, k - (mid2 - L2) - 1);
}
}
};
1 key point in findMedianSortedArrays()

It is **k = (m + n + 1) / 2.**

Let me give you examples here.

If the sum of lengths in 2 arrays is odd, the median is the (m + n + 1) / 2 one. (5 + 1) / 2 = 3.

1 2 3 4 5
m

If the sum of lengths in 2 arrays is even, the mid-left one is the (m + n + 1) / 2 one. (4 + 1) / 2 = 2. we need k + 1 one to calculate the median.

1 2 3 4
m
2 key points in findKth()

The first one is the logic to do binary search in both two arrays.

The second one is how to define the size of left part.

The (mid1 - L1) + (mid2 - L2) + 1 is actually meaning there should be two pointers in two arrays: one is the kth and another one is the one which makes the recursion end.

array1:
x x x x x x
n
array2:
x x x x x x x x
k
"merged one array"
x x x x x x x x x x x x x x
k

so we count the left of both pointers and the one where k is.

I think the code is simpler if we make if condition for k first, and then for nums1 or nums2.

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
int k = (len1 + len2 + 1) / 2; // for odd total it is the mid one, for even it is the left mid
int num1 = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k);
if ((len1 + len2) & 1) return num1;
int num2 = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k + 1);
return (num1 + num2) / 2.0;
}
private:
int findKth(vector<int>& nums1, int L1, int R1, vector<int>& nums2, int L2, int R2, int k) {
if (L1 > R1) return nums2[L2 + k - 1];
if (L2 > R2) return nums1[L1 + k - 1];
int mid1 = L1 + (R1 - L1) / 2, mid2 = L2 + (R2 - L2);
if (k <= (mid1 - L1) + (mid2 - L2) + 1) {
if (nums1[mid1] <= nums2[mid2]) return findKth(nums1, L1, R1, nums2, L2, mid2 - 1, k);
else return findKth(nums1, L1, mid1 - 1, nums2, L2, R2, k);
} else {
if (nums1[mid1] <= nums2[mid2]) return findKth(nums1, mid1 + 1, R1, nums2, L2, R2, k - (mid1 - L1) - 1);
else return findKth(nums1, L1, R1, nums2, mid2 + 1, R2, k - (mid2 - L2) - 1);
}
}
};
Complexity

I think we need to do binary search in both arrays, generally the complexity is log(m + n) for divide conquer. But actually it is not that much.