[LeetCode]4. Median of Two Sorted Arrays

原题链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

找到两组已排序数列的中间值。时间复杂度要为O(log (m+n)).

我的实现（不记得在哪篇大佬博客看到的方法）：

class Solution {
public:
    double findKSortedArrays(vector<int>& nums1, vector<int>& nums2, int nums1_start, int nums1_end, int nums2_start, int nums2_end, int k) {
        if (nums1_start > nums1_end) {
            return nums2[nums2_start + k - 1];
        }
        
        if (nums2_start > nums2_end) {
            return nums1[nums1_start + k - 1];
        }
        
        int nums1_mid = (nums1_start + nums1_end) / 2;
        int nums2_mid = (nums2_start + nums2_end) / 2;
        
        int count = nums1_mid - nums1_start + nums2_mid - nums2_start + 1;
        
        if (nums1[nums1_mid] <= nums2[nums2_mid]) {
            if (k <= count)
                return findKSortedArrays(nums1, nums2, nums1_start, nums1_end, nums2_start, nums2_mid - 1, k);
            else
                return findKSortedArrays(nums1, nums2, nums1_mid + 1, nums1_end, nums2_start, nums2_end, k - (nums1_mid - nums1_start + 1));
        } else {
            if (k <= count)
                return findKSortedArrays(nums1, nums2, nums1_start, nums1_mid - 1, nums2_start, nums2_end, k);
            else
                return findKSortedArrays(nums1, nums2, nums1_start, nums1_end, nums2_mid + 1, nums2_end, k - (nums2_mid - nums2_start + 1));
        }
        
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int nums1_size = nums1.size();
        int nums2_size = nums2.size();
        int size = nums1_size + nums2_size;
        
        if (size % 2 == 0) {
            return (findKSortedArrays(nums1, nums2, 0, nums1_size - 1, 0, nums2_size - 1, (int)(size/2)) +
                    findKSortedArrays(nums1, nums2, 0, nums1_size - 1, 0, nums2_size - 1, (int)(size/2) + 1)) / 2;
        } else {
            return findKSortedArrays(nums1, nums2, 0, nums1_size - 1, 0, nums2_size - 1, (int)(size/2) + 1);
        }
    }
};

思想：考虑到两个数组的个数总和有偶数与奇数两种情况，这个找中间数的问题实际上可以转为在两个数列中找到第k大的数；

因为有时间复杂度要求，所以暴力法求第k大的数是不能用的，我们这里使用的是二分查找，实现起来就是上面所示。

总结：找中间值转为找第K大的值，二分查找