//*************************
//三分检索
//*************************
#include<iostream.h>
#include<iomanip.h>
//*************************************
//检索给定的值x在有序数组A中出现的位置
//如果有，返回出现的位置，否则返回-1
//*************************************
int ThirdSearch(int A[],int x,int n)
{
int low,high,mid1,mid2;
low=0;
high=n;
while(low<=high)
{
mid1=int(low+(high-low)/3);
mid2=int(low+((high-low)/3)*2);
if(x<A[mid1]) high=mid1-1;
else if(x>A[mid1] && x<A[mid2]) {low=mid1+1;high=mid2-1;}
else if(x>A[mid2]) low=mid2+1;
else if(x==A[mid1]) return mid1;
else if(x==A[mid2]) return mid2;
}
return -1;
}
void main(void)
{
int n,x,i,*pa,result;
cout<<"Please Input The Number of Array: ";
cin>>n;
pa=new int [n];
cout<<"Please Input The Data of Array:"<<endl;
for(i=0;i<n;i++)
cin>>pa[i];
cout<<"Please Input The Number of Search Number:";
cin>>x;
cout<<endl<<"**************************************"<<endl;
cout<<"This Array have "<<n<<" Nubmers."<<endl;
for(i=0;i<n;i++)
cout<<setw(8)<<pa[i];
cout<<endl<<"The Search Number is: "<<x<<endl;
cout<<"****************************************"<<endl;
cout<<endl<<"The Result of Search is:"<<endl;
result=ThirdSearch(pa,x,n);
if(result==-1)
cout<<"There have not Number in This Array!"<<endl;
else
cout<<x<<" Location is "<<result<<endl;
cout<<"The Program is end"<<endl;
}
