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)).
Tags: Divide and Conquer, Array, Binary Search
分析：
对于数字个数k，如果k为奇数，则k个数的中位数为第（k/2+1）个；对于偶数，中位数为第k/2和（k/2+1）的平均数。
而对于两个有序数组a[m] b[n]，找其第i个数的方法是：第一个数组取出前i/2个数，第二个数组则取出前（i-i/2）个数（注意不一定等于i/2），然后比较各自最大的数，如果a[i/2-1]<b[i-i/2-1]，则a数组的前i/2个数全是第i个数之前的数，然后从a数组剩下（m-i/2）个数的子数组和b数组中继续取第（i-i/2）个数。
当然，这里可能会出现m<i/2的情形，这时a就取出其前m个数，b取出前i-m个数即可。对称的情况也可能出现在b上面，这时只需要更换下参数顺序即可。
最后说下终止条件，当m全取完即m==0时，就返回b[i-1]。当i/2-1<0即i<2时，无法继续细分（因为细分后要比较a[i/2-1]和b[i-i/2-1]），说明只需要从两个数组中取出第一个，则返回min(a[0],b[0])即可。
c++代码：
1 class Solution { 2 public: 3 double findIth(int A[], int m, int B[], int n, int i) { 4 if (m > n) 5 return findIth(B, n, A, m, i); 6 if (m == 0) { 7 return B[i - 1]; 8 } 9 if (i <= 1) { 10 return min(A[0], B[0]); 11 } 12 int aSeg = min(m, i / 2), bSeg = i - aSeg; 13 if (A[aSeg - 1] < B[bSeg - 1]) { 14 return findIth(A + aSeg, m - aSeg, B, n, i - aSeg); 15 } else if (A[aSeg - 1] > B[bSeg - 1]) { 16 return findIth(A, m, B + bSeg, n - bSeg, i - bSeg); 17 } else { 18 return A[aSeg - 1]; 19 } 20 } 21 double findMedianSortedArrays(int A[], int m, int B[], int n) { 22 int num = m + n; 23 if (num % 2 == 1) { 24 return findIth(A, m, B, n, num / 2 + 1); 25 } else { 26 return (findIth(A, m, B, n, num / 2 + 1) 27 + findIth(A, m, B, n, num / 2)) / 2; 28 } 29 } 30 };
原文：http://www.cnblogs.com/chen0958/p/4356371.html