给定两个大小分别为 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

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-10(6) <= nums1[i], nums2[i] <= 10(6)

中位数本质上是把这两个数组分成了两部分

左部分数<右部分数，且数量最多相差1

所以我们可以寻找一个i来划分nums1，根据m和n从而得到j来划分nums2

划分过后有nums1LR <= nums2RL且nums1RL >= nums2LR

当同时满足时就是正确划分

再寻找i的过程中，如果先满足了nums1LR <= nums2RL则此i可能正确也可能左边划分少了，此时我们更新l = i+1

如果连nums1LR <= nums2RL都没满足说明左边划分多了，更新r=i-1

同时注意只有在划分可能正确的情况下才更新ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public : double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int l = 0;
        int r = m;
        int leftMax = 0;
        int rightMin = 0;
        while (l <= r) {
            int i = (r - l) / 2 + l;
            int j = (m + n + 1) / 2 - i;

            int nums1LR = i == 0 ? INT_MIN : nums1[i - 1];
            int nums1RL = i == m ? INT_MAX : nums1[i];
            int nums2LR = j == 0 ? INT_MIN : nums2[j - 1];
            int nums2RL = j == n ? INT_MAX : nums2[j];

            if (nums1LR <= nums2RL) {
                leftMax = max(nums1LR, nums2LR);
                rightMin = min(nums1RL, nums2RL);
                l = i + 1;
            } else {
                r = i - 1;
            }
        }
        if ((m + n) % 2 == 0) {
            return (leftMax + rightMin) / 2.0;
        }
        return leftMax;
    }
};