题目

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

一、思路：使用二分查找

使用一条分割线把两个数组分别分割成两个部分：

划分分割线时应同时满足的条件是：（1）两个元素个数之和为偶数时：红线左边和右边元素个数相等；为奇数时：红线左边元素的个数比右边元素的个数多1 （ps：也可以右边比左边多1，看自己怎么定义）

（2）红线左边所有元素的数值<=红线右边所有元素的数值

如果满足以上两个条件，则两个数组的中位数就跟一个数组的中位数性质相等，即中位数就一定只与红线两侧的元素有关，确定这条红线的位置使用二分查找

具体而言：满足以上两个条件的前提下，如果数组个数之和为奇数，则红线左边最大的元素为中位数

如果满足以上两个条件的前提下，如果数组个数之和为偶数，则（红线左边最大的元素+红线右边最小的元素)/2=中位数

二、具体实现

1、实现条件（1）

假设数组1的长度为m，数组2的长度为n。

当m+n为偶数时，红线左边的元素个数为（m+n)/2 = (m+n+1)/2

当m+n为奇数时，红线左边的元素个数为（m+n+1)/2

因此，可以将以上两种写法合并，记为 $size_{left}$ =（m+n+1)/2，这样写的好处就是只需要确定其中一个数组的分割线位置，另一个数组的分割线位置可以通过公式推导出来。

2、实现条件（2）

我们主要是需要保证交叉小于等于关系成立，即第一个数组红线左边的第一个元素要<=第二个数组红线右边的第一个元素? and? 第二个数组红线左边的第一个元素<=第一个数组红线右边的第一个元素。

如果不满足上面交叉小于等于关系的话，那么我们就需要适当调整分割线的位置

以下为不满足条件（2）的两种情况

问题：第二个数组红线左边第一个元素>第一个数组红线右边第一个元素

解决方法：第一个数组红线右移，第二个数组红线左移

?问题：第一个数组红线左边的第一个元素>第二个数组红线右边的第一个元素

解决方法：第二个数组红线右移，第一个数组红线左移

3、几种特殊情况

三、代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 始终保证nums1为较短的数组，方便以后操作
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        
        int m = nums1.length;
        int n = nums2.length;

        // m+n 为奇数，分割线要求左侧有 (m+n)/2 + 1 个元素
        // m+n 为偶数，分割线要求左侧有 (m+n)/2     个元素
        // 两种情况其实可以统一写作 (m+n+1)/2，表示对(m+n)/2向上取整
        // 对整数来说，向上取整等于：(被除数 + (除数 - 1)) / 除数
       
        int leftTotal = (m + n + 1) / 2;
        int left = 0, right = m;
        while (left < right) {
            // +1 向上取整避免 left + 1 = right 时可能无法继续缩小区间而陷入死循环
            int i = left + (right - left + 1) / 2;
            int j = leftTotal - i;
            
            //要找最大i，使得nums1[i-1] <= nums2[j]
            //使用对立面缩小区间
            if (nums1[i - 1] > nums2[j]) {
                // [i+1, m]均不满足
                right = i - 1;
            } else {
                // i满足说明[0, i-1]均不为满足条件的最大i，舍去以缩小区间
                left = i;
            }
        }

        //退出循环时left=right，表示最终nums1中分割线的位置
        int i = left;
        //nums2中分割线的位置
        int j = leftTotal - left;
        System.out.println(i);

        //判断极端情况
        int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];  //nums1分割线左边没有元素
        int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];  //nums2分割线左边没有元素
        int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];     //nums1分割线右边没有元素
        int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];     //nums2分割线右边没有元素

        if ((m + n) % 2 == 0) {
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
        } else {
            return Math.max(nums1LeftMax, nums2LeftMax);
        }
    }
}