【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

:scream: :scream: :scream: 这道题很是爆炸，难度系数是hard。一开始的思路就是先合并两个数组，由于是有序数组，所以复杂度为O(m+n)，不符合题目要求啊，看到log(m+n)，能想到的算法就是二分查找了，于是想利用二分法的思想来解决这个问题，哎，可能是现在自己还太渣了，分析了好一会都没有能想到结果，写的代码提交运行总是得不到正确结果，就研究了下别人的思路，也是类似利用二分法，不过我还是没又搞清楚我自己的思路为什么写出来的代码运行结果不正确，自己写的代码最烦的就是边界的判定了，要吐血的感觉，所以下面代码的参考代码理解起来不难，而且没有繁杂的边界还有除法运算，整数除法什么的最烦了。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int size_1 = nums1.size();
        const int size_2 = nums2.size();
        int k = (size_1 + size_2) / 2;
        int res1 = Kth(nums1.begin(), size_1, nums2.begin(), size_2, k+1);
        if ((size_1 + size_2) % 2 == 0) {
            int res2 = Kth(nums1.begin(), size_1, nums2.begin(), size_2, k);
            return ( (double) res1 + res2) / 2.0;
        }
        return res1;
    }
private:
  typedef vector<int>::iterator Iter;

    int Kth(Iter a, int m, Iter b, int n, int k) {
        if(m > n)   return Kth(b,n,a,m,k);
        if(m == 0)  return *(b+k-1);
        if(k == 1)  return min(*a,*b);

        int pa = min(k/2,m);
        int pb = k - pa;

        if(*(a+pa-1) < *(b+pb-1)) return Kth(a+pa,m-pa,b,n,k-pa);
        else if(*(a+pa-1) > *(b+pb-1)) return Kth(a,m,b+pb,n-pb,k-pb);
        else return *(a+pa-1);
    }
};