寻找数组中的最大值和最小值

数组是最简单的一种数据结构。我们经常碰到一个基本的问题，就是寻找整个数组中的最大数或最小数。我们只需

遍历一遍数组，就能找到最大(最小)数。如果同时寻找最大数和最小数呢？对于一个由N个整数组成的数组，需要比较多少次才能把最大和最小的数找出来呢？

解法一：

可以把这个问题分解为两个问题，求最大值和最小值，我们可以遍历两边数组，第一遍求最大值，第二遍求最小值，时间复杂度为O(2*N)。

解法二：

我们可以在概念上把数组中相邻的两个元素分为一组，然后比较这两个元素，较大者和max比较，如果大于max则更新max，较小者和min比较，小于min则更新min。算法的时间复杂度为O(1.5*n)。例如：

实现代码：

void find_max_min(int *a, int length, int *max, int *min)
{
	if (length <= 0)
		return;

	if (length <= 1)
	{
		*max = *min = a[length-1];
		return;
	}

	/*初始化max和min*/
	*max = a[0] > a[1] ? a[0] : a[1];
	*min = a[0] > a[1] ? a[1] : a[0];
	int i;
	int n;

	if (length % 2)
		n = length - 1;
	else
		n = length;

	for (i = 2; i < n;i+=2)
	{
		if (a[i] > a[i+1])
		{
			*max = *max > a[i] ? *max : a[i];
			*min = *min > a[i + 1] ? a[i + 1] : *min;
		}
		else
		{
			*max = *max > a[i+1] ? *max : a[i+1];
			*min = *min > a[i] ? a[i] : *min;
		}
	}

	/*如果length为奇数，则剩下最后一个元素没有做过比较*/
	if (i < length)
	{
		*max = *max > a[i] ? *max : a[i];
		*min = *min > a[i] ? a[i] : *min;
	}
}

解法三：

分治思想是解决问题常用的一种技巧。我们可以先求出前n/2个数的max和min，然后求出后n/2个数的max和min，取较大的max和较小的min即可。算法时间复杂度为O(1.5*n)。

void find_max_min(int *a, int satrt, int end,int *max, int *min)
{
	if (end >= satrt)
	{
		if (end - satrt <= 1)
		{
			if (a[end] > a[satrt])
			{
				*max = a[end];
				*min = a[satrt];
			}
			else
			{
				*max = a[satrt];
				*min = a[end];
			}
			return;
		}
		int left_max, left_min, right_max, right_min;
		int mid = (satrt + end) / 2;

		find_max_min(a, satrt, mid, &left_max, &left_min);
		find_max_min(a, mid + 1, end, &right_max, &right_min);

		*max = left_max > right_max ? left_max : right_max;
		*min = left_min > right_min ? right_min : left_min;
	}
}