算法 - 有两个相同大小数组均已按升序排列好，编程计算这两个数组的中位数（C++）

/*
Let X[0..n-1] and Y[0..n-1] be the two arrays, each containing n numbers already in the sorted order.
Give an O(log n) time algorithm to find the median of all 2n elements in array X and Y.
*/

#include <iostream>

using namespace std;

template <typename T>
T median2 (T* X, T* Y, int size)
{
	int m = (size - 1) / 2;
	if (X[m] == Y[m])
	{
		return X[m];
	}
	else if (X[m] > Y[m])
	{
		return size == 1 ? Y[m] : median2 (X, Y + size - m - 1, m + 1);
	}
	else
	{
		return size == 1 ? X[m] : median2 (X + size - m - 1, Y, m + 1);
	}
}

void main()
{
	int a[6] = {1, 2, 3, 7, 19};
	int b[6] = {12, 13, 25, 28, 33};
	int median = median2(a, b, 5);
	cout << median << endl;
}

// Output:
/*
12
*/