要求求得数组中第二大数
采用分治思想解决这个问题
#include<iostream>
using namespace std;
//分治思想求数组中第二大的数
//low为数组低位索引，high为数组高位索引
void search(int *a,int low,int high,int *max,int *smax)
{
//max为最大的数，smax为数组中第二大的数
if(high-low<=1)
{
if(a[low]<a[high])
{
*max=a[high];
*smax=a[low];
return;
}
else
{
*max=a[low];
*smax=a[high];
return;
}
}
int lmax,lsmax,rmax,rsmax;
//lmax定义为数组左半边最大的数
//lsmax为数组左半边第二大的数
//rmax定义为数组右半边最大的数
//rsmax定义为数组右半边第二大的数
//搜索数组左半边
search(a,low,low+(high-low)/2,&lmax,&lsmax);
//搜索数组右半边
search(a,low+(high-low)/2+1,high,&rmax,&rsmax);
if(lmax>rmax)
{
if(rmax>lsmax)
{
*max=lmax;
*smax=rmax;
}
else
{
*max=lmax;
*smax=lsmax;
}
}
else
{
if(lmax>rsmax)
{
*max=rmax;
*smax=lmax;
}
else
{
*max=rmax;
*smax=rsmax;
}
}
return;
}
int main()
{
int a[8]={9,7,4,6,3,19,11,12};
int smax,max;
search(a,0,7,&max,&smax);
cout<<max<<" "<<smax<<endl;
//for test output
cin>>max;
return 0;
}