C++算法：寻找两个正序数组的中位数

class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
const int Len = nums1.size() + nums2.size();
const int iAvg1 = Rec(nums1.data(), nums1.data() + nums1.size(), nums2.data(), nums2.data() + nums2.size(), (Len - 1) / 2);
if (Len & 1)
{
return iAvg1;
}
const int iAvg2 = Rec(nums1.data(), nums1.data() + nums1.size(), nums2.data(), nums2.data() + nums2.size(), (Len - 1) / 2+1);
return (iAvg1 + iAvg2) / 2.0;
}
int Rec(int* b1, int* e1, int* b2, int* e2, int iFindIndex)
{
if (b1 == e1)
{
return b2[iFindIndex];
}
if (b2 == e2)
{
return b1[iFindIndex];
}
if (0 == iFindIndex)
{
return min(*b1, *b2);
}
int k = (iFindIndex + 1) / 2;
const int index1 = min(k - 1,(int)( e1 - b1)-1);
const int index2 = min(k - 1, (int)(e2 - b2 )- 1);
if (b1[index1] < b2[index2])
{
return Rec(b1 + index1 + 1, e1, b2, e2, iFindIndex - index1 - 1);
}
return Rec(b1, e1, b2 + index2 + 1, e2, iFindIndex - index2 - 1);
}
};

class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
m_c = nums1.size() + nums2.size();
m_iHalf = m_c / 2;
int left = 0, r = min(m_iHalf, (int)nums1.size()) + 1;//左闭右开
while (r > left + 1)
{
const auto mid = left + (r - left) / 2;
const int leftLen2 = m_iHalf - mid;
const int iRet = Cmp(mid, leftLen2, nums1, nums2);
if (0 == iRet)
{
break;
}
else if (iRet < 0)
{
r = mid;
}
else
{
left = mid;
}
}
if (m_dRet < 0 )
{
Cmp(left,m_iHalf-left,nums1,nums2);
}
return m_dRet;
}
int Cmp(int leftLen1, int leftLen2, const vector& nums1, const vector& nums2)
{
if (leftLen2 > nums2.size())
{
return 1;
}
int iLeftMax = INT_MIN;
if (leftLen1 > 0)
{
iLeftMax = max(iLeftMax, nums1[leftLen1 - 1]);
}
if (leftLen2 > 0)
{
iLeftMax = max(iLeftMax, nums2[leftLen2 - 1]);
}
int iRightMin = INT_MAX;
if (leftLen1 < nums1.size())
{
iRightMin = min(iRightMin, nums1[leftLen1]);
}
if (leftLen2 < nums2.size())
{
iRightMin = min(iRightMin, nums2[leftLen2]);
}
if (iLeftMax <= iRightMin)
{
if (1 & m_c)
{
m_dRet = iRightMin;
}
else
{
m_dRet = (iLeftMax + iRightMin) / 2.0;
}
return 0;
}
if ((leftLen1 > 0) && (nums1[leftLen1 - 1] > iRightMin))
{
return-1;
}
return 1;
}
double m_dRet=-1;
int m_c;
int m_iHalf;
};