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

编程之美有一道是关于寻找数组中的最大值和最小值的题目，该作者提供了四种思路解法：
第一种思路：
直接暴力遍历寻找数组中的最大值和最小值，该算法比较次数为2*N次。
第二种思路：
首先按顺序将数组中相邻的两个数分在同一组，例如数组为{5,6,8,3,7,9},按其思路分组，其结果如图所示：

接着比较同一组中奇数位数字和偶数位数字，将较大的数放在偶位数上，较小的数放在奇数位上，经过N/2次比较后，较大的数都放到了偶数位置上，较小的数则放到了奇数位置上。如图：

最后，再奇数位和偶数位置上分别寻找最小值和最大值，各需要比较次数是N/2,故整个算法比较次数是1.5*N.
第三种思路：
这种和第二种思路一样，只不过这第三种避免了破坏原数组的元素位置，它利用两个变量Max和Min来存储当前的最大值和最小值，同一组两个数比较之后，不再调整顺序，而是将其中较小的数与当前Min作比较，如果该数小于当前Min则更新Min，同理将其中较大的数与当前Max做比较，如果该数大于当前Max，则更新Max，整个算法过程的比较次数也是1.5*N.如图所示：

第四种思路：
采用分治思想，分别求出前后Ｎ／２个数的Min和Max，然后取较小的Min，较大的Max即可(只需较大的数和较大的数比较，较小的数和较小的数比较，两次就可以了)。对于整个算法比较次数,我们可以用 logaN 性质和等比数列求和公式推导下面公式：
f(2)=1
f(N)=2∗f(N/2)+2=2∗(2∗f(N/22)+2)+2=22∗f(N/22)+22+2⋯=2(log2N)−1∗f(N/2(log2N)−1)+2(log2N)−1+⋯+22+2=N2∗f(2)+2(log2N)−1+⋯+22+2=N2∗f(2)+2∗(1−2(log2N)−1)1−2=N2+2∗(1−N2)1−2=1.5N−2
代码实现：

#include <iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
void search(int *arr,int b,int e,int &max,int &min)
{
//前半部分的最大值和最小值存储
int maxL,minL;
//后半部分的最大值和最小值存储
int maxR,minR;
//边界
if(e-b<=1)
   {
if(arr[b]>arr[e])
      {
max=arr[b];
min=arr[e];
      }
else
      {
max=arr[e];
min=arr[b];
      }
return ;
   }
//b+(e-b)/2相当于(b+e)/2,不过b+(e-b)/2可以防止溢出
   search(arr,b,b+(e-b)/2,maxL,minL);//前半部分
//cout << "front: "<<"b: "<<b<<" b+(e-b)/2: "<<b+(e-b)/2<<" MAX IS: "<<maxL<<" MIN IS: "<<minL<< endl;
   search(arr,b+(e-b)/2+1,e,maxR,minR);//后半部分
// cout << "rear: "<<"b+(e-b)/2+1: "<<b+(e-b)/2+1<<" e: "<<e<<" MAX IS: "<<maxR<<" MIN IS: "<<minR<< endl;
//比较前半部分和后半部分的最大值和最小值
if(maxL>maxR)
   {
max=maxL;
   }
else
   {
max=maxR;
   }
if(minL<minR)
   {
min=minL;
   }
else
   {
min=minR;
   }
//cout <<"result: "<< "MAX IS: "<<max<<" MIN IS: "<<min<< endl;
}
int main()
{
int arr[6]={6,5,8,3,9,7};
int max,min;
    search(arr,0,5,max,min);
    cout << "MAX IS: "<<max<<" MIN IS: "<<min<< endl;
return 0;
}

就拿上面的数组arr数字分析，上面的算法相当于树的后序遍历，每次分割一次，树增加的结点就是2的n次方(其中n 为分割前树的宽度)，如图：