算法 || 分治法【寻找两个等长有序序列的中位数】#03

算法 || 分治法【寻找两个等长有序序列的中位数】#03 寻找两个等长有序序列的中位数

目录

• 寻找两个等长有序序列的中位数
• • 【问题描述】
  • 【算法讲解】
  • 【完整代码】
  • 【运行结果】

【问题描述】

对于一个长度为n的有序序列（假设均为升序序列）a[0…n-1]，处于中间位置的元素称为a的中位数。设计一个算法求给定的两个有序序列的中位数。

例如，若序列a=(11，13，15，17，19)，其中位数是15，
若b=(2，4，6，8，20)，其中位数为6。两个等长有序序列的中位数是含它们所有元素的有序序列的中位数。例如a、b两个有序序列的中位数为11。 a=(11，13，15，17，19) b=(2，4，6，8，20)

c=(2，4，6，8，11，12，15，17，19，20)

【算法讲解】

对于含有n个元素的有序序列a[s…t]，当n为奇数时，中位数是出现在m=(s+t)/2处；当n为偶数时，中位数下标有m=(s+t)/2（下中位）和m=(s+t)/2+1（上中位）两个。为了简单，仅考虑中位数为m=(s+t)/2处。

采用二分法求解。
分别求出 a，b 的中位数 a[m1]，b[m2]：
情形1：若a[m1]=b[m2]，则a[m1]或b[m2]即为所求中位数，算法结束。
情形2：若a[m1] 情形3：若a[m1]>b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。

【完整代码】

VS2017 C++

#include
using namespace std;
#define MAXN 15

//取a[s..t]序列的前半个子序列
void prepart(int& s, int& t)
{
	int m = (s + t) / 2;
	t = m;
}
//取a[s..t]序列的后半个子序列
void backpart(int& s, int& t)
{
	int m = (s + t) / 2;
	//序列中有奇数个元素
	if ((s + t) % 2 == 0)
		s = m;
	//序列中有偶数个元素
	else
		s = m + 1;
}
//求中位数
int midnum(int a[], int s1, int t1, int b[], int s2, int t2)
{
	int m1, m2;
	if (s1 == t1 && s2 == t2)
		return a[s1] < b[s2] ? a[s1] : b[s2];
	else
	{
		m1 = (s1 + t1) / 2;//序列1的中位数
		m2 = (s2 + t2) / 2;//序列2的中位数
		if (a[m1] == b[m2])
			return a[m1];//若两个中位数相等则返回该中位数
		else if (a[m1] < b[m2])
		{
			backpart(s1, t1);//序列1取后半部分
			prepart(s2, t2);//序列2取前半部分
			return midnum(a, s1, t1, b, s2, t2);
		}
		else
		{
			backpart(s2, t2);//序列2取后半部分
			prepart(s1, t1);//序列1取前半部分
			return midnum(a, s1, t1, b, s2, t2);
		}
	}
}
int main()
{
	int n;
	int a[MAXN], b[MAXN];
	cout << "请输入数组的大小：";
	cin >> n;
	cout << "请依次输入数组1数据：";
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << "请依次输入数组2数据：";
	for (int i = 0; i < n; i++)
		cin >> b[i];
	cout << "中位数是：" << midnum(a, 0, n-1, b, 0, n-1) << endl;
	system("pause");
	return 0;
}

【运行结果】