求数组的最大值和最小值

给定一个含有n个元素的整型数组a，找出其中的最大值和最小值

常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。

 

代码：

//  : 定义控制台应用程序的入口点。
//

#include ""
#include <iostream>
using namespace std;

// 求数组的最大值和最小值，返回值在maxValue和minValue
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
{
	if(l == r) // l与r之间只有一个元素
	{
		maxValue = a[l] ;
		minValue = a[l] ;
		return ;
	}

	if(l + 1 == r) // l与r之间只有两个元素
	{
		if(a[l] >= a[r])
		{
			maxValue = a[l] ;
			minValue = a[r] ;
		}
		else
		{
			maxValue = a[r] ;
			minValue = a[l] ;
		}
		return ;
	}

	int m = (l + r) / 2 ; // 求中点

	int lmax ; // 左半部份最大值
	int lmin ; // 左半部份最小值
	MaxandMin(a, l, m, lmax, lmin) ; // 递归计算左半部份

	int rmax ; // 右半部份最大值
	int rmin ; // 右半部份最小值
	MaxandMin(a, m + 1, r, rmax, rmin) ; // 递归计算右半部份

	maxValue = max(lmax, rmax) ; // 总的最大值
	minValue = min(lmin, rmin) ; // 总的最小值
}

int main()
{
	int a[]={1,2,3,4,-4,2,6,3};
	int len = sizeof(a)/sizeof(int);
	int max,min;
	MaxandMin(a,0,len-1,max,min);
	cout<<max<<" "<<min<<endl;
	system("pause");
	return 0;
}