// using divide and conquer idea, each time find the mid of both arrays
double findMedianSortedArrays(int A[], int m, int B[], int n) {
/* A[0, 1, 2, ..., n1, n] */
/* A[0, 1, 2, ..., m1, m] */
int k = (m + n + 1) / 2;
double v = (double)FindKth(A, 0, m  1, B, 0, n  1, k);
if ((m+n) % 2 == 0) {
int k2 = k+1;
double v2 = (double)FindKth(A, 0, m  1, B, 0, n  1, k2);
v = (v + v2) / 2;
}
return v;
}
// find the kth element int the two sorted arrays
// let us say: A[aMid] <= B[bMid], x: mid len of a, y: mid len of b, then wen can know
//
// (1) there will be at least (x + 1 + y) elements before bMid
// (2) there will be at least (m  x  1 + n  y) = m + n  (x + y +1) elements after aMid
// therefore
// if k <= x + y + 1, find the kth element in a and b, but unconsidering bMid and its suffix
// if k > x + y + 1, find the k  (x + 1) th element in a and b, but unconsidering aMid and its prefix
int FindKth(int A[], int aL, int aR, int B[], int bL, int bR, int k) {
if (aL > aR) return B[bL + k  1];
if (bL > bR) return A[aL + k  1];
int aMid = (aL + aR) / 2;
int bMid = (bL + bR) / 2;
if (A[aMid] <= B[bMid]) {
if (k <= (aMid  aL) + (bMid  bL) + 1)
return FindKth(A, aL, aR, B, bL, bMid  1, k);
else
return FindKth(A, aMid + 1, aR, B, bL, bR, k  (aMid  aL)  1);
}
else { // A[aMid] > B[bMid]
if (k <= (aMid  aL) + (bMid  bL) + 1)
return FindKth(A, aL, aMid  1, B, bL, bR, k);
else
return FindKth(A, aL, aR, B, bMid + 1, bR, k  (bMid  bL)  1);
}
}
Share one divide and conquer O(log(m+n)) method with clear description



@shichaotan  Can you explain your algorithm using examples. For instance why do you start with k= (m+n+1)/2. Also how do you derive to complexity O(log(m+n))? Thanks in advance.

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 midleft 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.