2020-02-05

int findKthEle( vector<int> & nums1, vector<int> & nums2, int k )
{
    int first = max( 0, k - nums2.size() ), last = min( nums1.size(), k );
    /* 我们寻找的是满足a[i-1]<=b[j]&&b[j-1]<=a[i]的最小的位置i */
    while ( first < last )
    {
        int mid = first + (last - first) / 2;
        /*
         * m=i，j=k-m,所以i+j=k，k-m-1相当于j-1即j前一个位置。j-1比i位置的值大，需要排除
         * 只需判断 b[j-1]<=a[i] 这个条件
         * 因为找的是最小的i，j=k-i是所有满足b[j-1]<=a[i]中相对最大的
         * 如果它不满足其他的也不可能满足另一个条件
         * 所以一定满足a[i-1]<=b[j]，不满足的都会在逼近过程中排除
         */
        if ( nums2[k - mid - 1] > nums1[mid] )
            first = mid + 1;
        else last = mid;
    }

    /*
     * 循环结束时的位置first即为所求位置
     * 第k小即为max(nums1[first-1]),nums2[k-first-1])
     * 但是由于le可以为0、k，first-1或者k-first-1可能不存在
     */
    int nums1_max   = first == 0 ? INT_MIN : nums1[first - 1];
    int nums2_max   = first == k ? INT_MIN : nums2[k - first - 1];
    return(max( nums1_max, nums2_max ) );
}

double findMedianSortedArrays( vector<int> & nums1, vector<int> & nums2 )
{
    int n = nums1.size() + nums2.size();
    double  median;
    if ( n & 1 )    /* 奇数 */
    {
        median = findKthEle( nums1, nums2, n / 2 + 1 );
    } else {        /* 偶数 */
        median = (findKthEle( nums1, nums2, n / 2 ) + findKthEle( nums1, nums2, n / 2 + 1 ) ) / 2.0;
    }

    return(median);
}