D&C

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/
参考文献：

• 求两个有序数组的中位数-算法导论
• 求两个有序数组的中位数或者第k小元素

思路：
实在是脑子转不过来，看了一下解法，然后就把自己的理解讲一下吧。
有两个规律需要说下：
1.在某个数列头尾删去相同数量的元素，其中位数是不变的。比如[1,2,3,4]删去1和4.
2.如果两个数列的中位数是m1, m2，那么合并后的数列的中位数的值肯定在[m1,m2]范围内。
既然题目是要Log级别的复杂度，就要想到要用折半法把问题的规模降低…举个例子，假设有[1,2,4,6,6,8]和[1,5,7,8,10,25,36]两个数列，很容易算出他们的（前序 ）中位数分别是4和8，而他们合并后的中位数的值在[4,8]之间。
然后可以删去无用的值，[1,2]与[10,25,36]. 但由于规律1的限制，如果后面删了3个的话，合并后删减的数列会发生变化（本例中奇偶性都变了），我们只能删去min(2,3)=2个元素…这种删值从理论上讲就是折半了，然后搞一波递归就行了。
最最最基本的思路如下：

两个有序数列Ary1, Ary2（假设升序排列）的中位数分别为m1,m2
if m1 == m2:
    LUCKY!!!
elif m1 < m2:
    取（Ary1的后半段，Ary2的前半段）再算
else
    取（Ary1的前半段，Ary2的后半段）再算

由于题设里面俩数组是不等长的，所以里对其中某个数组n<=2时处理方法需要注意…
代码：

int max(int x, int y) {
    return x>y ? x : y;
}
int min(int x, int y) {
    return x<y ? x : y;
}
double getMedian(int* nums, int size) {
	if (size == 0)
		return -1;
	if (size % 2 == 0) {
		//Even number
		return (nums[size / 2] + nums[size / 2 - 1]) / 2.0;
	}
	else {
		return nums[(size - 1) / 2];
	}
}
double findMedianMerge(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int count = 0;
	int n1Count = 0;
	int totalSize = nums1Size + nums2Size;
	int t1, t2;
	if (totalSize % 2 == 0) {
		t1 = totalSize / 2;
		t2 = t1 + 1;
	}
	else {
		t1 = -1;
		t2 = totalSize / 2 + 1;
	}
	double sum = 0;
	int curVal;
	while (n1Count < nums1Size) {
		if (*nums1 < *nums2) {
			n1Count++;
			curVal = *nums1;
			nums1++;
		}
		else {
			curVal = *nums2;
			nums2++;
		}
		count++;
		if (count == t1 || count == t2) {
			sum += curVal;
		}
		else if (count >= t2) {
			break;
		}
	}
	if (count < t1) {
		//Not finished
		nums2 += (t1 - count - 1);
		count = t1;
		sum += *nums2;
		nums2++;
	}
	if (count < t2) {
		nums2 += (t2 - count - 1);
		sum += *nums2;
	}
	if (t1 == -1)
		return sum;
	else
		return sum / 2.0;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int totalSize = nums1Size + nums2Size;
	if (nums1Size > nums2Size) {
		//Keep ary1 shorter than ary2
		int* temp = nums1;
		int t = nums1Size;
		nums1 = nums2;
		nums1Size = nums2Size;
		nums2 = temp;
		nums2Size = t;
	}
	if (nums1Size == 0) {
		return getMedian(nums2, nums2Size);
	} else if (nums1Size == 1) {
		if (nums2Size == 1) {
			return (nums1[0] + nums2[0]) / 2.0;
		}
		else {
			return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
		}
	}
	else if (nums1Size == 2) {
		if (nums2Size == 2) {
			return (max(nums1[0], nums2[0]) + min(nums1[1], nums2[1])) / 2.0;
		}
		else {
			return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
		}
	}
	//Slice
	double m1 = getMedian(nums1, nums1Size);
	double m2 = getMedian(nums2, nums2Size);
	if (m1 == m2) {
		//Got lucky
		return m1;
	}
	else if (m1 < m2) {
		//Slice L-nums1 and R-nums2
		int cut = (nums1Size - 1) / 2;
		return findMedianSortedArrays(nums1 + cut, nums1Size - cut, nums2, nums2Size - cut);
	}
	else {
		//Slice R-nums1 and L-nums2
		int cut = (nums1Size - 1) / 2;
		return findMedianSortedArrays(nums1, nums1Size - cut, nums2 + cut, nums2Size - cut);
	}
}