难度：困难
给定两个大小为m和n的有序少数组nums1和nums2。
请找出这两个有序数组的中位数。要求算法的时间复杂度为O(log(m+n))。
你可以假设nums1和nums2不同时为空

C语言实现：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size);

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int nums1[] = {3};
        int nums2[] = {-2,-1};
        int length1 = sizeof(nums1)/sizeof(int);
        int length2 = sizeof(nums2)/sizeof(int);
        double result = findMedianSortedArrays(nums1,length1,nums2,length2);
        printf("%f",result);
        printf("\n");
    }
    return 0;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    if (nums1>nums2) {
        int* temp = nums1;nums1 = nums2;nums2 = temp;
        int tmp = nums1Size;nums1Size = nums2Size;nums2Size = tmp;
    }
    int iMin = 0, iMax = nums1Size, halfLen = (nums1Size+nums2Size+1)/2;
    while (iMin <= iMax) {
        int i = (iMin+iMax)/2;
        int j = halfLen - i;
        if(i < iMax && nums2[j-1]>nums1[i]){
            iMin = i + 1;
        }else if(i > iMax && nums1[i-1]>nums2[j]){
            iMin = i - 1;
        }else{
            int maxLeft = 0;
            if(i==0){
                maxLeft = nums2[j-1];
            }else if(j==0){
                maxLeft = nums1[i-1];
            }else{
                maxLeft = nums1[i-1]>nums2[j-1]?nums1[i-1]:nums2[j-1];
            }
            if ((nums1Size+nums2Size)%2==1) {
                return maxLeft;
            }
            
            int minRight = 0;
            if (i==nums1Size) {
                minRight = nums2[j];
            }else if(j==nums2Size){
                minRight = nums1[i];
            }else{
                minRight = nums2[j]>nums1[i]?nums1[i]:nums2[j];
            }
            return (maxLeft+minRight)/2.0;
        }
    }
    return 0;
}

Java实现：

public class topic4 {

    public static void main(String[] args) {
        int[] A = {3};
        int[] B = {-2,-1};
        double result = findMedianSortedArrays(A,B);
        System.out.println("result:"+result);
    }
    public static double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}