LeetCode 4

原题如下：

There are two sorted arrays nums1 and nums2 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)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

简单方法：可以将两个有序数组做归并排序，然后找到中间元素并计算结果。其时间复杂度为O(n)，空间复杂度为O(n)。

更好一点的办法，是使用二分法。由于数组是有序的，可以利用这一特性，二分搜索找到这样的数，将两个数组平均的分成两半。通常情况下，算法复杂度为O(logn)，空间复杂度为O(1)。具体算法见如下代码：

 1     private int findNthSortedArrays(int A[], int as, int B[], int bs, int n){
 2         while(n>1 && as < A.length && bs < B.length){
 3             int half = n/2;
 4             if(as + half > A.length){
 5                 half = A.length - as;
 6             }
 7             if(bs + half > B.length){
 8                 half = B.length - bs;
 9             }
10             if(A[as+half-1] > B[bs+half-1]){
11                 bs = bs + half;
12             }else{
13                 as = as + half;
14             }
15             n = n - half;
16         }
17         if(as >= A.length){
18             return B[bs + n-1];
19         }else if(bs >= B.length){
20             return A[as+n-1];
21         }
22         return A[as]>B[bs]?B[bs]:A[as];
23     }
24 
25 
26     public double findMedianSortedArrays(int A[], int B[]) {
27         int len = A.length+B.length;
28         if(len%2 == 0){
29             int m1 = findNthSortedArrays(A, 0, B, 0, len/2);
30             int m2 = findNthSortedArrays(A, 0, B, 0, len/2+1);
31             return ((double)m1+m2)/2;
32         }else{
33             return findNthSortedArrays(A, 0, B, 0, len/2+1);
34         }
35     }

参考源码：https://github.com/pkufork/Martians/blob/master/src/main/java/com/pkufork/martians/leetcode/L4_MedianofTwoSortedArrays.java