Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

 

思路：首先注意一点，这里所谓的”the median of the two sorted arrays”，对于m+n为奇数的情况，就是指第(m+n+1)/2个数，如果m+n为偶数，则是指第(m+n)/2和第(m+n)/2+1个数的平均数。

 

本题时间要求是O(log(m+n))，因此每次都需要排除一半的可能性。要得到两个排序数组的第(m+n)/2个数，考虑更广泛的问题，如何得到两个排序数组的第k个数？

如果k=1，则比较nums1[0]和nums2[0]，取较小者为结果。

如果k=2，则排除nums1[0]和nums2[0]中的较小者；更为一般的k>2，比较nums1[k/2-1]和nums2[k/2-1]，如果nums1[k/2-1]更小，则可以证明nums1[k/2-1]肯定不会是第k个数，因为在从nums1[0]---nums1[k/2-1]，以及从nums2[0]---nums2[k/2-1]这k个数中，小于nums1[k/2-1]的数最多只有k-2个。所以，这样就可以排除nums1[0]---nums1[k/2-1]这些数。然后就依次排除下去，当然还需要注意一些边界条件，比如nums1的长度小于k/2等，代码如下：

int findkth(int *set1, int len1, int *set2, int len2, int k)
{
	int n1, n2;

	if(len1>len2)
	{
		return findkth(set2, len2, set1, len1, k); 
	}

	if(len1 == 0)	return set2[k-1];
	
	if(k == 1)	return (set1[0]<set2[0])?set1[0]:set2[0];

	n1 = (k/2<len1)?k/2:len1;
	n2 = k-n1;

	if(set1[n1-1] < set2[n2-1])
	{
		return findkth(set1+n1, len1-n1, set2, len2, k-n1);
	}
	else if(set1[n1-1] > set2[n2-1])
	{
		return findkth(set1, len1, set2+n2, len2-n2, k-n2);
	}
	else
	{
		return set1[n1-1];
	}
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) 
{
	if((nums1Size+nums2Size)%2)
		return findkth(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size+1)/2);
	else
		return (findkth(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size)/2) +
			findkth(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size)/2+1))/2.0;
}