分治与递归-竞标赛思想

在一个有序数组中查询一个最大的数最优的时间复杂度是多少？ O(logn)

在一个无序数组中查询一个最大的数最优的时间复杂度是多少？ O(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 i,flag=1;
    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])
                bmax=num[i];
        }
    }
    return bmax;
}
int main()
{
    int i,l;
    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]);
        for(i=l;i<2*l;++i)
            m[i]=(i-l);
        max=work(l,2*l-1);
        bmax=work2(l,max);
        printf("the max is %d and the bmax is %d\n",max,bmax);
    }

    return 0;
}