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

思路：

这道题在边界条件那里花了很长的时间，总算AC了。大概思路就是实现一个函数，找两个数组第k大的数，每次从判断A数组的中间的数在B中大几个数，然后递归。

代码：

 1     double findSortedArrays(int A[], int la, int ra, int B[], int lb, int rb, int k){
 2         if(la >= ra)
 3             return B[lb+k-1];
 4         if(lb >= rb)
 5             return A[la+k-1];
 6         int a = (la+ra)/2;
 7         int mid, left =  lb, right = rb;
 8         mid = (lb+rb)/2;
 9         while(lb < rb){
10             if(B[mid] > A[a])
11                 rb = mid;
12             else if(B[mid] < A[a])
13                 lb = mid+1;
14             else
15                 break;    
16             mid = (lb+rb)/2;
17         }
18         if(a-la+mid-left > k-1)
19             return findSortedArrays(A, la, a, B, left, mid, k);
20         else if(a-la+mid-left < k-1){ 
21             return findSortedArrays(A, a+1, ra, B, mid, right, k-a+la-mid+left-1);
22         }
23         return A[a];
24     }
25     double findMedianSortedArrays(int A[], int m, int B[], int n) {
26         if((m+n)%2)
27             return findSortedArrays(A, 0, m, B, 0, n, (m+n)/2+1);
28         return (findSortedArrays(A, 0, m, B, 0, n, (m+n)/2)+findSortedArrays(A, 0, m, B, 0, n, (m+n)/2+1))/2;
29     }

在网上搜索，发现一个更简单的思路。也是找第k大的元素，不过他的实现方式是比较A的第k/2-1个数和B的第k/2-1个数，如果前者小，那个前者砍掉前一半（前一半肯定都小于第k个数，可反证），如果后者小，则砍掉后者数组的前一半。否则就是结果。

在实际操作的时候，k/2可能大于数组本身，需要去k/2和数组的长度的较小值。如果一个数组长度为0，或者k为1可以直接返回答案。

这个算法的最坏情况是，每次剪掉k/2个值，所以复杂度是O(lg(m+n))。更好的情况是，直接剪掉某个数组的全部，那么能更快地达到结果。所以平均复杂度仍是O(lg(m+n))。

代码如下：

 1     double findKth(int A[], int m, int B[], int n, int k){
 2         if(m > n)
 3             return findKth(B, n, A, m, k);
 4         if(m == 0)
 5             return B[k-1];
 6         if(k == 1)
 7             return min(A[0], B[0]);
 8         int a = min(k/2, m), b = k-a;
 9         if(A[a-1] < B[b-1])
10             return findKth(A+a, m-a, B, n, k-a);
11         else if(A[a-1] > B[b-1])
12             return findKth(A, m, B+b, n-b, k-b);
13         return A[a-1];
14     }
15     double findMedianSortedArrays(int A[], int m, int B[], int n) {
16         if((m+n)%2)
17             return findKth(A, m, B, n, (m+n)/2+1);
18         return (findKth(A, m, B, n, (m+n)/2)+findKth(A, m, B, n, (m+n)/2+1))/2;
19     }