分治法

道家:”一生二,二生三,三生万物!”–《道德经》
分治二分检索
[cpp]
//二分检索算法,查找元素520是否在数列中，是’YES’,否’NO’;
#include <iostream>
using namespace std;
int main()
{
int n,*p;
cout<<“输入元素个数:”;cin>>n;
p=new int[n];
for(int i=0;i<n;i++) cin>>p[i];
int low=0,high=n-1,mid,number=0;
while(low<=high)
{
mid=(low+high)/2;
if(p[mid]<520) low=mid+1;
else if(p[mid]>520) high=mid-1;
else {number=mid;break;}
}
if(number) cout<<“YES 下标:”<<number<<endl;
else cout<<“NO”<<endl;
delete[] p;
return 0;
}

[/cpp]

分治求最大值和最小值
[cpp]

#include <iostream>
using namespace std;
void divide(int i,int j,int &max,int &min,int *&p)
{
int max1,min1,max2,min2,mid;
if(i==j) max=min=p[i];
else if(i==j-1) if(p[i]>p[j]) {max=p[i];min=p[j];}
else {max=p[j];min=p[i];}
else
{
mid=(i+j)/2;
divide(i,mid,max1,min1,p);
divide(mid+1,j,max2,min2,p);
max=(max1>max2?max1:max2);
min=(min1<min2?min1:min2);
}
//cout<<“MAX:”<<max<<endl;
}
int main()
{
int n,*p;cin>>n;
p=new int[n];
for(int i=0;i<n;i++) cin>>p[i];
int max,min;
divide(0,n-1,max,min,p);
cout<<max<<” “<<min<<endl;
delete[] p;
return 0;
}

[/cpp]