[LeetCode] Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

思路：难题
定义C为A和B合并而成的sorted array
m+n 奇数时：median为C第 (m+n)/2+1 个数
m+n 偶数时：median为C第 (m+n)/2 和第 (m+n)/2+1 个数的平均
问题转化为：如果已知A、B，和任意1<=k<=m+n，找到C中第k个数。其中C=sorted(merge(A,B))
比较A，B中任意两个数字A[i]，B[j]。假设A[i]，B[j]为C中第i'和j'个数。
1. 如果A[i] < B[j]：
B[j] > A[0:i]以及B[j]>=B[0:j-1] => B[j] => j' >= i+j+2
A[i] >= A[0:i-1]以及A[i]最多比B[0:j-1]大 => i' <= i+j+1
k> i+j+1，A[0:i]可以排除
k<= i+j+1，B[j:n-1]可以排除
2. 如果A[i] > B[j]：和1正好相反
k > i+j+1，B[0:j]可以排除 
k<= i+j+1，A[i:m-1]可以排除
3. 如果A[i] = B[j]：
A[i]>=A[0:i-1]，A[i]>=B[0:j] => i' >= i+j+2
B[j]和A[i]的情况一样 j' >= i+j+2
k > i+j+1，A[0:i]可以排除（假如i' = i+j+2，k = i+j+2，由于A[i]=B[j]两者都可以为第i+j+2个数字，所以A[i]可以排除掉）
k <= i+j+1，B[j:n-1]可以排除
所以3可以合并到1中。

思路整理：
A[i] <= B[j]
k > i+j+1，搜索A[i+1:m-1]和B[0:n-1]中的第k-i-1个元素
k <= i+j+1，搜索A[0:m-1]和B[0:j-1]中的第k个元素
A[i] > B[j]
k > i+j+1，搜索A[0:m-1]和B[j+1:n-1]中的第k-j-1个元素
k <= i+j+1，搜索A[0:i-1]和B[0:n-1]中的第k个元素
base case: 
如果搜索A[s:e]且s>e，即A搜索完了，则直接返回B[k-1]。
如果搜索B[s:e]且s>e，即B搜索完了，则直接返回A[k-1]。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int mid = (m+n)/2; if((m+n)%2) // odd total length return (double)findKthNum(A, m, B, n, mid+1); else { int median1 = findKthNum(A, m, B, n, mid); int median2 = findKthNum(A, m, B, n, mid+1); return 0.5*((double)median1 + (double)median2); } } int findKthNum(int A[], int m, int B[], int n, int k) { if(m==0) return B[k-1]; if(n==0) return A[k-1]; int i = m/2, j = n/2; if(A[i]<=B[j]) { if(k>i+j+1) return findKthNum(A+i+1, m-i-1, B, n, k-i-1); else return findKthNum(A, m, B, j, k); } else { if(k>i+j+1) return findKthNum(A, m, B+j+1, n-j-1, k-j-1); else return findKthNum(A, i, B, n, k); } } };