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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

方法一：二分查找

主要难点在于题目要求的时间复杂度O(log (m+n)) ，因此不能使用暴力枚举合并两个数组的方法找到中位数，采用二分查找算法。

二分查找的标准框架如下：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

最常用场景为二分搜索，即搜索一个数，如存在返回其索引，否则返回-1：

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意索引

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 舍弃索引值小于mid以及包括mid的所有数字，左边界刷新为mid的下一位
        else if (nums[mid] > target)
            right = mid - 1; // 注意索引值大于mid以及包括mid的所有数字，右边界刷新为mid的前一位
        }
    return -1;
}

解题思路如下：

有三种特殊情况需要注意：

官方解答如下：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + 
                            getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;

        while(true){

            if(index1 == length1){
                return nums2[index2 + k - 1];
            }
            if(index2 == length2){
                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, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if(pivot1 <= pivot2){
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else{
                k -= (newIndex2 -index2 + 1);
                index2 = newIndex2 + 1;
            }
        }

    }
}

编写代码时有几点需要注意：

1. 尤其注意数组的数字个数与数组索引的区分，通常为 数字索引 = 数字个数 -1， 更新索引时注意是否需要-1，以及每次更新左边界索引时要在 pivot 的基础上+1；
2. 对于 index1 == length1 时返回 nums2[index2 + k -1] 的理解：

当 index1 = length1 时，此时的 index2 等于上一次循环中的 k/2, 而 k 经过更新后也为上一次循环中的 k/2,此时 index + k 即为左边界起第 k 个数字，去索引后 -1.