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

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 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)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治算法 
// 👍 3768 👎 0

/*
* 4 寻找两个正序数组的中位数
* 2021-03-06 11:42:51
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
// [ref]:https://zxi.mytechroad.com/blog/algorithms/binary-search/leetcode-4-median-of-two-sorted-arrays/
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);
        const int k = (n + m + 1) / 2; // 左中位数


        int l = 0;int r = m;
        while(l < r){
            const int a = l + (r - l) / 2;
            const int b = k - a;

            if(nums1[a] < nums2[b-1]){
                l = a + 1;
            }else
                r = a;
        }

        const int a = l;
        const int b = k - l;

        const int c = max(a <= 0 ? INT_MIN : nums1[a-1],
                          b <= 0 ? INT_MIN : nums2[b-1]);

        if((m + n) % 2 == 1) return c;

        const int d = min(a >= m ? INT_MAX : nums1[a],
                          b >= n ? INT_MAX : nums2[b]);

        return (c + d) * 0.5;
    }
};
//leetcode submit region end(Prohibit modification and deletion)