【数据结构与算法分析习题7.40-查找最大最小元】

template 
vector findMinMax(vector& a, int low, int high)
{
	if (low > high)
	{
		return {};
	}
	else if (low == high)
	{
		return { a[low], a[low] };
	}
	else if (high - low == 1)
	{
		Comparable max = a[low] > a[high] ? a[low] : a[high];
		Comparable min = a[low] > a[high] ? a[high] : a[low];
		return { max, min };
	}
	else
	{
		int l = low, r = high;
		int mid = low + ((high - low) >> 1);
		vector LmaxMin = findMinMax(a, l, mid);
		vectorRmaxMin = findMinMax(a, mid + 1, r);
		Comparable max = LmaxMin[0] > RmaxMin[0] ? LmaxMin[0] : RmaxMin[0];
		Comparable min = LmaxMin[1] < RmaxMin[1] ? LmaxMin[1] : RmaxMin[1];
		return { max, min };
	}
}

int main()
{
	srand(time(0));
	vector vint;
	for (int i = 0; i < 25000; i++)
	{
		vint.push_back(rand() % 30000 - 20);
	}
	vector maxMin = findMinMax(vint, 0, 10000 - 1);
	cout << "Max: " << maxMin[0] << endl
		<< "Min: " << maxMin[1] << endl;
}