leetcode 4. 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]

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

问题转换为求第k小的值问题。假设有2个数组一共有5个数，那么第3小的值就是中位数。假设有2个数组6个数，那么第3小和第4小的数的平均值就是其中位数。

题目要求用O(log(n+m))的时间复杂度，可以用二分去解决(参考网上).
思路：首先假设数组a和b的元素个数都大于k/2，我们比较a[k/2-1]和b[k/2-1]两个元素，这两个元素分别表示a的第k/2小的元素和b的第k/2小的元素。
这两个元素比较共有三种情况：>、<和=。如果a[k/2-1]<b[k/2-1]，这表示a[0]到a[k/2-1]的元素都在a和b合并之后的前k小的元素中。换句话说，a[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。

当a[k/2-1]>b[k/2-1]时存在类似的结论。抛弃b数组的前k/2个元素。

当a[k/2-1]=b[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素.
还有一些边界情况：
如果a或者b为空，则直接返回b[k-1]或者a[k-1]；
如果k为1，我们只需要返回a[0]和b[0]中的较小值；
如果a[k/2-1]=b[k/2-1]，返回其中一个

代码如下：

class Solution {
public:
    int findK(vector<int>& a, int as, int n, vector<int>& b, int bs, int m, int k) {
        if (n > m) return findK(b, bs, m, a, as, n, k);
        if (n == 0) return b[bs+k-1];
        if (k == 1) return min(a[as], b[bs]);
        int l = min(n, k/2); 
        int r = k - l;
        if (a[as+l-1] > b[bs+r-1]) {
            return findK(a, as, n, b, bs+r, m-r, k-r);
        } else if (a[as+l-1] < b[bs+r-1]){
            return findK(a,  as+l, n-l, b, bs, m, k-l);
        } else {
            return a[as+l-1];
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int k = (n+m)/2;
        if ((m+n)%2 == 1) {
            return findK(nums1, 0, n, nums2, 0, m, k+1);
        }
        else {
            return (findK(nums1, 0, n, nums2, 0, m, k) + findK(nums1, 0, n, nums2, 0, m, k+1)) / 2.0;
        }
    }
};