查找两个有序数组合并后的中位数

例题 ：查找两个有序数组合并后的中位数
【题目】 两个有序数组查找合并之后的中位数。给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组合在一起之后的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空，所有的数字全都不相等。还可以再假设，如果数字个数为偶数个，中位数就是中间偏左的那个元素。

例如：nums1 = [1, 3, 5, 7, 9]

nums2 = [2, 4, 8, 12]

输出 5。

【解析】 这个题目是我个人非常喜欢的，原因是，它所有的解法和思路，都隐含在了题目的描述中。如果你具备很强的分析和解决问题的能力，那么一定可以找到最优解法。

我们先看一下复杂度的分析。这里的 nums1 和 nums2 都是有序的，这让我们第一时间就想到了归并排序。方法很简单，我们把两个数组合并，就得到了合在一起后的有序数组。这个动作的时间复杂度是 O(m+n)。接着，我们从数组中就可以直接取出中位数了。很可惜，这并不满足题目的时间复杂度 O(log(m + n)) 的要求。

接着，我们来看一下这个问题的定位。题目中有一个关键字，那就是“找出”。很显然，我们要找的目标就藏在 nums1 或 nums2 中。这明显就是一个查找问题。而在查找问题中，我们学过的知识是分治法下的二分查找。

回想一下，二分查找适用的重要条件就是，原数组有序。恰好，在这个问题中 nums1 和 nums2 分别都是有序的。而且二分查找的时间复杂度是 O(logn)，这和题目中给出的时间复杂度 O(log(m + n)) 的要求也是不谋而合。因此，经过分析，我们可以大胆猜测，此题极有可能要用到二分查找。

我们再来看一下数据结构方面。如果要用二分查找，就需要用到若干个指针，去约束查找范围。除此以外，并不需要去定义复杂的数据结构。也就是说，空间复杂度是 O(1) 。

好了，接下来，我们就来看一下二分查找如何能解决这个问题。二分查找需要一个分裂点，去把原来的大问题，拆分成两个部分，并在其中一部分继续执行二分查找。既然是查找中位数，我们不妨先试试以中位数作为切分点，看看会产生什么结果。如下图所示：

经过切分后，两个数组分别被拆分为 3 个部分，合在一起是 6 个部分。二分查找的思路是，需要从这 6 个部分中，剔除掉一些，让查找的范围缩小。那么，我们来思考一个问题，在这 6 个部分中，目标中位数一定不会发生在哪几个部分呢？

中位数有一个重要的特质，那就是比中位数小的数字个数，和比中位数大的数字个数，是相等的。围绕这个性质来看，中位数就一定不会发生在 C 和 D 的区间。

如果中位数在 C 部分，那么在 nums1 中，比中位数小的数字就会更多一些。因为 4 < 5（nums2 的中位数小于 nums1 的中位数），所以在 nums2 中，比中位数小的数字也会更多一些（最不济也就是一样多）。因此，整体来看，中位数不可能在 C 部分。同理，中位数也不会发生在 D 部分。

接下来，我们就可以在查找范围内，剔除掉 C 部分（永远比中位数大的数字）和 D 部分（永远比中位数小的数字），这样我们就成功地完成了一次二分动作，缩小了查找范围。然而这样并没结束。剔除掉了 C 和 D 之后，中位数有可能发生改变。这是因为，C 部分的数字个数和 D 部分数字的个数是不相等的。剔除不相等数量的“小数”和“大数”后，会造成中位数的改变。

为了解决这个问题，我们需要对剔除的策略进行修改。一个可行的方法是，如果 C 部分数字更少为 p 个，则剔除 C 部分；并只剔除 D 部分中的 p 个数字。这样就能保证，经过一次二分后，剔除之后的数组的中位数不变。

应该剔除 C 部分和 D 部分。但 D 部分更少，因此剔除 D 和 C 中的 9。

二分查找还需要考虑终止条件。对于这个题目，终止条件必然是某个数组小到无法继续二分的时候。这是因为，每次二分剔除掉的是更少的那个部分。因此，在终止条件中，查找范围应该是一个大数组和一个只有 1～2 个元素的小数组。这样就需要根据大数组的奇偶性和小数组的数量，拆开 4 个可能性：

可能性一：nums1 奇数个，nums2 只有 1 个元素。例如，nums1 = [a, b, c, d, e]，nums2 = [m]。此时，有以下 3 种可能性：

如果 m < b，则结果为 b；

如果 b < m < c，则结果为 m；

如果 m > c，则结果为 c。

这 3 个情况，可以利用 "A?B:C" 合并为一个表达式，即 m < b ? b : (m < c ? m : c)。

可能性二：nums1 偶数个，nums2 只有 1 个元素。例如，nums1 = [a, b, c, d, e, f]，nums2 = [m]。此时，有以下 3 种可能性：

如果 m < c，则结果为 c；

如果 c < m < d，则结果为 m；

如果m > d，则结果为 d。

这 3 个情况，可以利用"A?B:C"合并为一个表达式，即 m < c ? c : (m < d? m : d)。

可能性三：nums1 奇数个，nums2 有 2 个元素。例如，nums1 = [a, b, c, d, e]，nums2 = [m,n]。此时，有以下 6 种可能性：

如果 n < b，则结果为 b；

如果 b < n < c，则结果为 n；

如果 c < n < d，则结果为 max(c,m)；

如果 n > d，m < c，则结果为 c；

如果 n > d，c < m < d，则结果为 m；

如果 n > d，m > d，则结果为 d。

其中，4～6 可以合并为，如果 n > d，则返回 m < c ? c : (m < d ? m : d)。

可能性四：nums1 偶数个，nums2 有 2 个元素。例如，nums1 = [a, b, c, d, e, f]，nums2 = [m,n]。此时，有以下 6 种可能性：

如果 n < b，则结果为 b；

如果 b < n < c，则结果为 n；

如果 c < n < d，则结果为 max(c,m)；

如果 n > d，m < c，则结果为 c；

如果 n > d，c < m < d，则结果为 m；

如果 n > d，m > d，则结果为 d。与可能性 3 完全一致。

不难发现，终止条件都是 if 和 else 的判断，虽然逻辑有点复杂，但时间复杂度是 O(1) 。为了简便，我们可以假定，nums1 的数字数量永远是不少于 nums2 的数字数量。

因此，我们可以编写如下的代码：

#include<stdio.h>

int find(int* a,int begina,int enda,int* b,int beginb,int endb){
	
	int lengtha = enda - begina + 1;
	int lengthb = endb - beginb + 1;
	int mid = (enda + begina) / 2;
	//如果 a, b都只剩一个元素
	if(lengtha == 1 ){
		return a[begina]<b[beginb]?a[begina]:b[beginb];
	} 
	//如果a，b都剩两个元素
	if(lengtha == 2 ){
		if(a[begina] < b[beginb]){
			return a[enda] < b[beginb] ? a[enda] : b[beginb];
		}else{
			return b[endb] < a[begina] ? b[endb] : a[begina];
		}
	} 
	//假定a的元素个数大于b的元素个数
	//当b的个数为1时 a的个数为偶数时 
	if((lengtha % 2 == 0 )&& (lengthb == 1)){
		int m = b[beginb];
		int c = a[mid];
		int d = a[mid + 1];
		return m < c ? c : (m < d ? m : d);
	}
	//当b的个数为1时， a的个数为奇数时 
	if((lengtha % 2 == 1) && (lengthb == 1)){
		int bb = a[mid - 1];
		int c = a[mid];
		int m = b[beginb];
		return m < bb ? bb : (m < c ? m : c);
	
	}
	//当b的个数为2时，a的个数为奇数或偶数的判断情况是一样的 
	if(lengthb == 2){
		int bb = a[mid - 1];
		int c = a[mid];
		int d = a[mid + 1];
		
		int m = b[beginb];
		int n = b[endb];
		if(n < bb){
			return bb;
		}else if(n < c){
			return n;
		}else if(n < d){
			return c > m ? c : m;
		}else{
			return m < c ? c : (m < d ? m : d);
		}
	}
	
	
	
	//划分
	int mida = (begina + enda) / 2;
	int midb = (beginb + endb) / 2;
	
	//划分原则 中位数比一组中间数大的小（在左边）， 比一组中间数小的大（在右边），两组增删一致，按b的即元素少的那一组 
	if( a[mida] < b[midb]){
		int steps = endb - beginb;
		return find(a,begina + steps,enda,b,beginb,endb - steps);
	} else{
		int steps = midb - beginb;
		return find(a,begina,enda - steps,b,beginb + steps,endb);
	}
}

int main(){
	int a[] = {1,2,3,4,5};
	int b[] = {6,7,8,9};
	int lengtha = sizeof(a) / sizeof(a[0]);
	int lengthb = sizeof(b) / sizeof(b[0]);
	printf("两组有序数列的合并数列中位数为%d\n",find(a,0,lengtha - 1,b,0,lengthb - 1));
	return 0;
}