??
我们知道，在一个容量为n的数据集合中寻找一个最大数，不管用什么样的比较算法，至少要比较n-1次，就算是用竞标赛排序也得比较n-1次，否则你找到的就不能保证是最大的数。那么，在一个容量为n的数据集合中同时寻找最大数和最小数的最小比较次数是多少呢？
???? 从一个容量为n的数据集合中同时找到最大数和最小数的最优方法是：首先让所有的元素参与两两比较，这样总共比较了n/2次，最大数肯定在胜者组中，最小数肯定在败者组中；然后从容量为n/2的胜者组中找到最大的数，最少要比较n/2 - 1次；同理，从容量为n/2的败者组中找到最小的数，最少要比较n/2 - 1次。所以总共需要比较
(3n/2) - 2次。以上假设n为偶数。奇数同理。
这是同时寻找最大数和最小数的最优算法。
?
??? 那么，我们要从一个容量为n的数据集（假设该数据集是一个集合，即没有相同的元素）中找到第二大元素需要多少次比较呢？
??? 一种习惯的方法是：先找出最大的元素，这需要比较n-1次；然后从剩下的n-1个元素中找到最大的，这个元素就是我们要找的第二大元素，这需要比较n-2次。做一总共比较2n-3次。
但是，
??? 还有一个更优的方法：
（1） 我们考虑淘汰赛的比较法，淘汰赛结束后，找出冠军我们需要n-1次比较；如下图所示，找到12需要比较7次。
（2） 此时我们要考虑到，亚军应该存在于败给冠军的这些选手中（否则，每个元素都至少有两个元素比它大），由于与冠军比过的元素个数为┌log2n┐，从这些元素中找到最大值需要比较┌log2n┐ - 1次；如下图所示，亚军应该在10,11,4这三个元素中。否则，如果亚军是5，那么冠军12比它大，与它比较过的10也比它大，至少两个元素大于5，所以5肯定不是亚军的候选者。
?
（3）从而找出亚军要比较n-1+┌log2n┐-1 = n-2+┌log2n┐次比较。这个算法是寻找亚军的最优算法。
分治与递归——最大值和次大值的最优算法
问题描述：输入n个数，最坏情况下用?n + logn - 2?次比较找出当中的最大值和次大值。
算法思想：根据题意出现logn，则肯定用到二分或者堆的思路，但是输入的数没有经过排序，而且题目要求的计算量也不允许排序。这样，就肯定会用到类似堆的思路，但是直接构造堆等同于排序。堆的思想跟竞标赛类似，都是父节点>=（<=）子节点。如果父节点都是从子节点而来，这样就是竞标赛；如果不是，这样就是堆。既然不能排序又不能构造堆，那就只能用竞标赛的思想，通过二分来进行最多logn次竞赛，选出最大值（冠军），而次大值（亚军）只能在与最大值的比较中被淘汰（亚军的实力只可能输给冠军），故在所有被最大值（冠军）淘汰的数值中选取次大值，最多也是logn次比较，满足题意（由于题意只限制了比较次数，故实现过程并没有考虑时间复杂度和空间复杂度）
代码实现：
//最大值和次大值的最优算法,数组中可能存在重复元素,不能处理最大值是0的情况
#include <stdio.h>
#define N 1000
int m[2*N];
int num[2*N];
int biaoji[N];
int bigger(int i)
{
????if(num[i]>num[i+1])
????{
????????biaoji[m[i+1]]=num[i];
????????return i;
????}
????else
????????biaoji[m[i]]=num[i+1];
????????return i+1;
}
int work(int a,int b)
????int i,j;
????while(a<b)
????????for(i=a;i<b;i+=2)
????????{
????????????j=bigger(i);
????????????num[i/2]=num[j];
????????????m[i/2]=m[j];
????????}
????????if(i==b)
????????????num[i/2]=num[i];
????????????m[i/2]=m[i];
????????a=a/2;
????????b=b/2;
????return num[a];
int work2(int l,int max)
????int bmax;
????for(i=l;i<2*l;++i)
????????if(biaoji[i-l]==max)
????????????if(flag)
????????????{
????????????????flag=0;
????????????????bmax=num[i];
????????????}
????????????else if(bmax<num[i])
????return bmax;
int main()
????int max,bmax;
????int f,start;
????while(true)
????????printf("please putin the length:n");
????????scanf("%d",&l);
????????if(l==0)
????????????break;
????????printf("please putin num[]:n");
????????for(i=l;i<2*l;++i)
????????????scanf("%d",&num[i]);
????????????m[i]=(i-l);
????????max=work(l,2*l-1);
????????bmax=work2(l,max);
????????printf("the max is %d and the bmax is %dn",max,bmax);
?
????return 0;
}
