Median of Two Sorted Arrays

题目：
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]

解答：

假定两个数组中的数组个数均多于k/2个(代码中解释为什么多余k/2个，暂时先往下看吧)，咱们分别把两个数组中的第k/2-1个取出来，分别记作A[k/2 - 1]和B[k/2 -1],把他们进行比较，有三个结果（这不是废话吗？）

A[k/2 - 1] < B[k/2 - 1]

A[k/2 - 1] = B[k/2 - 1]

A[k/2 - 1] > B[k/2 - 1]

下面考虑第一种情况，A的第k/2个数（数组下标为k/2 - 1）比B的第k/2个数要小，说明当A和B合并之后，A的下标从0到k/2 - 1之间的数都不可能是第K大的数,显然咱们可以将它们剔除掉，有些人可能立马就想到了，这不就是二分查找的思想吗？我可以说是的，就是这么个意思。大于的情况是一样讨论的；等于的话打就更好了，不就直接就找到了吗？免得那么麻烦。有人可能现在产生疑惑了，奇数个和偶数个需要分开来讨论吗？其实是没必要的，合并之后是奇数个的话咱们直接就取正中间的那个，合并之后如果有偶数个数的话，咱们就将两个数加起来除以2.0不就OK啦。

下面我们来考虑一下递归的边界条件：

1）如果其中有一个数组是空的话，那么就直接返回另外一个数组的下标为[k - 1]的就可以了；

2）如果k = 1，也就是说取的是最小值，我们只需要比较A[0]和B[0]，然后取他们之间更小的值就行了呗；

3）如果A[k/2 - 1] = B[k/2 - 1],当然只需要返回其中的一个就行了。

 1 class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         int len1 = nums1.length;
 4         int len2 = nums2.length;
 5         
 6         int total = len1 + len2;
 7         if(total % 2 != 0) {
 8             return findKth(nums1, 0, len1-1, nums2, 0, len2-1, total/2+1);
 9         } else {
10             double result1 = findKth(nums1, 0, len1-1, nums2, 0, len2-1, total/2);
11             double result2 = findKth(nums1, 0, len1-1, nums2, 0, len2-1, total/2+1);
12             return (result1+result2)/2.0;
13         }
14     }
15     
16     private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
17         int length1 = end1 - start1 + 1;
18         int length2 = end2 - start2 + 1;
19         
20         if(length1 > length2) {
21             return findKth(nums2, start2, end2, nums1, start1, end1, k);
22         }
23         
24         if(length1 == 0) {
25             return nums2[start2 + k -1];
26         }
27         
28         if(k == 1) {
29             return Math.min(nums1[start1], nums2[start2]);
30         }
31         
32         int p1 = Math.min(k/2, length1);
33         int p2 = k - p1;
34         
35         if(nums1[start1+p1-1] < nums2[start2+p2-1]) {
36             return findKth(nums1, start1+p1, end1, nums2, start2, end2, k-p1);
37         } else if(nums1[start1+p1-1] > nums2[start2+p2-1]) {
38             return findKth(nums1, start1, end1, nums2, start2+p2, end2, k-p2);
39         } else {
40             return nums1[start1+p1-1];
41         }
42     }
43 }