[数据结构与算法]leetcode 4. 寻找两个正序数组的中位数(二分加速)

有点慢

class Solution {
public:

  int findKth(vector<int>& nums1,int i, vector<int>& nums2, int j, int k){
        if(i >= nums1.size())
        return nums2[j + k - 1];
        if(j >= nums2.size())
        return nums1[i + k - 1];

        if(k == 1)
        return min(nums1[i],nums2[j]);
    
        int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
        int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }
        else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
  }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (findKth(nums1, 0 ,nums2, 0, l) + findKth(nums1,0,nums2,0,r)) / 2.0;

    }

  
};

二分优化

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int n = nums1.size();
		int m = nums2.size();

		if (n > m)  //保证数组1一定最短 //为了加快速度 对长度短的进行二分
		{
			return findMedianSortedArrays(nums2, nums1);
		}
		int LMax1 = 0, LMax2 = 0, RMin1 = 0, RMin2 = 0, c1, c2, lo = 0, hi = n;
		while (lo <= hi) {
			c1 = (hi + lo + 1) / 2;
			c2 = (m + n) / 2 - c1;

			LMax1 = (c1 == 0) ? INT_MIN : nums1[c1 - 1];
			RMin1 = (c1 == n) ? INT_MAX : nums1[c1];
			LMax2 = (c2 == 0) ? INT_MIN : nums2[c2 - 1];
			RMin2 = (c2 == m) ? INT_MAX : nums2[c2];

			if (LMax1 > RMin2)
				hi = c1 - 1;
			else if (LMax2 > RMin1)
				lo = c1 + 1;
			else
				break;
		}
		if ((m + n) % 2)
			return min(RMin1, RMin2);
		else
			return ((int64_t)max(LMax1, LMax2) + (int64_t)min(RMin1, RMin2)) / 2.0;
	}
};