算法1

(递归) $O(logn)$

代码是yxc老师的，我只是把我读代码时遇到的问题写成注释以及写一些自己的思考，方便大家学习
注意：
1.明确问题，我们是要从两个数组找到第 m+n/2 小的数，记为k
2.k为偶数和k为奇数的情况
3.边界问题

参考文献

yxc代码

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0) //偶数情况，需要找到中间两个数相加除二
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else // 奇数情况，只需找到中位数
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        // 始终保持第一个数组的大小 < 第二个数组的大小，方便处理边界
        // 保证只有nums1会越界，即当前位置 i 加上 k/2 大于数组长度
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);

        // 如果nums1为空，则直接返回nums2
        if (nums1.size() == i) return nums2[j + k - 1];

        // 如果k = 1，则只需找一个数，比较两个数组的第一个数即可
        if (k == 1) return min(nums1[i], nums2[j]);

        // 判断i + k / 2是否大于数组大小，如果大于，则就以数组大小作为“k/2”
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;

        if (nums1[si - 1] > nums2[sj - 1])
        {
            // sj -j = sj - 1 - j + 1, 表示区间长度，这个区间已经被"取出来了"
            // 我们只需要再找第 k - (sj - 1 - j + 1) 小的数即可，
            // 新的和旧的凑起来就等于两个数组第k小的数
            return findKthNumber(nums1, i, nums2, j + k / 2, k - (sj - j));
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};