学步园

找到一个数组中最大值一般用如下方法，首先拿出数组中第一个值作为当前的最大值，然后依次和后面所有的值比较，发现有比当前最大值还大的就更新最大值的记录：

int maximum(int *arr, int size)<br /> {<br /> int i;<br /> int max = arr[0];<br /> for (i = 1; i < size; i++)<br /> {<br /> if (max < arr[i]) max = arr[i];<br /> }<br /> return max;<br /> } 

同理，最小值也是这么判断：

int minimum(int *arr, int size)<br /> {<br /> int i;<br /> int min = arr[0];<br /> for (i = 1; i < size; i++)<br /> {<br /> if (min > arr[i]) min = arr[i];<br /> }<br /> return min;<br /> } 

无论是求最大值还是最小值都进行了n-1次比较，那么同时求最大值是否需要判断2n-2次呢？

算法导论第九章给出了一个结论，最多只需要比较3+n-2次比较就可以完成，因为我们可以从数组中一次取两个数据，先将这两个数据进行比较，然后把其中大的与最大值记录比较，小的与最小值记录比较即可，因为取出的两个数据中的小的值不可能还会成为最大值。

void getRange(int *arr, int size, int *max, int *min)<br /> {<br /> int *p = arr, *endp = arr + size;<br /> if (size % 2 != 0)<br /> {<br /> *max = *min = *p++;<br /> }<br /> else<br /> {<br /> if (*p > *(p + 1))<br /> {<br /> *max = *p;<br /> *min = *(p + 1);<br /> }<br /> else<br /> {<br /> *max = *(p + 1);<br /> *min = *p;<br /> }<br /> p += 2;<br /> }<br /> while (p != endp)<br /> {<br /> if (*p > *(p + 1))<br /> {<br /> if (*p > *max) *max = *p;<br /> if (*(p + 1) < *min) *min = *(p + 1);<br /> }<br /> else<br /> {<br /> if (*(p + 1) > *max) *max = *(p + 1);<br /> if (*(p) < *min) *min = *p;<br /> }<br /> p += 2;<br /> }<br /> }