求两个等长有序数组的中位数的logN算法 分治法

题目：有两个长为n的非递减数组A和B，把B接在A的后面变成长为2n的数组C。设计算法求C的中位数（第n小数）。

思路：O(n)的算法很容易找到，关键是用二分的思想设计logn算法。这题关键是用好a和b数组中脚标和为定值的元素的大小关系。

直观想法是：如果中位数在数组a中，那么若a[m]<b[n-m-2]，此时比a[m]小的数最多只有n-2个，即a[m]不可能为第n小数，偏小更新左界;若a[m]> b [n-m-1],此时比a[m]小的数至少有n个，a[m]不可能为第n小数，偏大更新右界;若a[m]介于b[n-m-2]与b [n-m-1]则a[m]恰好为第n小数。中位数在数组b中的情况类似。

#include <iostream>
using namespace std;

int findNthNumber(int a[], int b[], int n){
	int l = 0, r = n -1;
	int m;
	while(l <= r){
		m = (l + r) / 2;
		if(m == n - 1 || a[m] < b[n - m -2]){
			//此时比a[m]小的数最多只有n-2个，即a[m]不可能为第n小数，偏小更新左界
			l = m + 1;
		}
		else if (a[m] < b [n - m - 1]){
			//此时比a[m]小的数恰好有n-1个，a[m]就是第n小数，返回
			return a[m];
		}
		else r = m - 1;//此时比a[m]小的数至少有n个，即a[m]不可能为第n小数，偏大更新右界
	}
	//中位数在b数组中的情况，和上面类似
	l = 0, r = n -1;
	while(l <= r){
		m = (l + r) / 2;
		if(m == n - 1 || b[m] < a[n - m -2]){
			l = m + 1;
		}
		else if (b[m] < a [n - m - 1]){
			return b[m];
		}
		else r = m - 1;
	}
}

int main(){
	int  a[] = {1, 3, 4, 9, 11, 20, 21};
	int  b[] = {2, 7, 8, 10, 70, 76, 79};
	cout<<findNthNumber(a, b, 7)<<endl;	
	return 0;
}

也可以取a[m]与b[n-m-2]中较大的一个，然后与a[m+1]和b[n-m-1]作比较，简化后的代码如下

#include <iostream>
using namespace std;

int findNthNumber(int a[], int b[], int n){
	int l = 0, r = n -1;
	int m, tmp;
	while(l <= r){
		m = (l + r) / 2;
		tmp = (a[m] < b [n - m - 2] ? b[n - m - 2] : a[m]);
		//tmp取a[m]与b[n-m-2]中较大的一个，然后与a[m+1]和b[n-m-1]作比较
		if(tmp > b [n - m - 1]){
			r = m - 1;
		}
		else if(tmp > a [m + 1]){
			l = m + 1;
		}
		else return tmp;
	}
}

int main(){
	int  a[] = {1, 3, 10, 11, 12, 20, 21};
	int  b[] = {2, 7, 8, 9, 70, 76, 79};
	cout<<findNthNumber(a, b, 7)<<endl;	
	return 0;
}