4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

本题如果没有复杂度要求，那会极其简单，用双指针遍历的复杂度也不会搞，就O(m+n)，可是如果是有了这个log的复杂度要求，那就非常难了。很明显的排序树组+对数复杂度要求，那必定就是用二分查找法。
但是本道题要想简单的从low,mid,high突破，是不可能的，因为有两个数组，你就算取出了两个数组的最小值和最大值，你不知道中间值究竟会在哪里。除非你将这两个数组同时放在一个数组里，但是那样又要用新的空间，而且在放数组的过程中就已经O(m+n)的复杂度了。
我自己也做不出来，看了题解之后也是考虑了很久的边界问题才完善了答案。

本题有个很巧妙的二分查找法，利用了中位数的概念。
如果有n个数字，如果是奇数，那中位数就是第n/2+1 个最小的数。
如果是偶数，中位数就是第n/2个最小的数，和第n/2+1最小的数的平均数。
我们直接把题目转化为求k。 第k个数是我们要求的。这里的k可能等于n/2可能等于n/2+1。
如何求k呢？
我们可以把k/2分别分配给两个数组。我们拿nums1[k/2-1] 和 nums2[k/2-1]，在这两个数以及之前的数一共有k个。(如果k是偶数，奇数不是k个，但是做法一致，为了讨论方便就先这么假设。)
我们要求的答案是第k个数。假如说，nums1[k/2-1] < nums2[k/2-1]。 那也就是说nums[k/2-1]一定不是第k小的数。最坏情况下，nums2[k/2-2]小于nums[k/2-1]的情况下，它也只是第k-1小的数。那在nums[k/2-1]之前的更加不可能是答案了。因此我们直接可以删去之前的数了，它们不可能是答案。我们在此基础上求第k个数，这个k的大小肯定要减少，原因是我们在此基础上只需要求第k-(删去数的个数)就可以了。
方法就是这样，但是我们还需要好好考虑边界问题。
-1、如果已经删光了一个数组的所有数，那k该怎么求呢？其实这样就很简单了，就直接去另外一个数组直接拿到那个第k个数就可以了。
-2、什么时候退出这个循环？ k=1的时候退出循环，因为可以直接拿到答案。
-3、一定要考虑清楚下标和第k小的数，下标对应的关系。
代码如下:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int totalLen = m + n;
        if (totalLen % 2 == 1){
            int mid = totalLen / 2;
            return findKth(nums1,nums2,mid+1);
        }
        else {
            int mid = totalLen / 2;
            return (findKth(nums1,nums2,mid)+findKth(nums1,nums2,mid+1)) / 2;
        }

    }
    //第k个小的数
    public double findKth(int[] nums1,int[] nums2,int k){
        int m = nums1.length;
        int n = nums2.length;
        int index1 = 0, index2 = 0;
        while (true){
            if (index1 == m){
                return nums2[index2 + k - 1];
            }
            if (index2 == n){
                return nums1[index1 + k - 1];
            }
            if (k == 1){
                return Math.min(nums1[index1],nums2[index2]);
            }

            int half = k / 2;
            int newindex1 = Math.min(index1+half,m)-1;
            int newindex2 = Math.min(index2+half,n)-1;

            if (nums1[newindex1] < nums2[newindex2]){
                k = k - (newindex1-index1 + 1);
                index1 = newindex1 + 1;
            }
            else{
                k = k - (newindex2 - index2 + 1);
                index2 = newindex2 + 1;
            }

        }
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。