注意二分法查找的前提是要已经排行序。
//递归二分法
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int a[Max],key;
int Search(int bot,int top)
{
int mid;
if(top>=bot)
{
mid=(top+bot)/2;
if(key==a[mid])
{
cout<<mid<<endl;
return 0;
}
else if(key>a[mid])
{
Search(mid+1,top);
}
else
{
Search(bot,mid-1);
}
}
else
{
printf("-1\n");
return 0;
}
}
int main()
{
freopen("half.in","r",stdin);
freopen("half.out,"w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
cin>>key;
Search(1,n);
return 0;
}
//非递归二分法
#include<iostream>
#include<cstdlib>
#define MAXN 10001
using namespace std;
int key,top,bot,mid,n,a[MAXN];
void Half()
{
top=n;
bot=1;
while(bot<=top)
{
mid=(bot+top)/2;
if(key==a[mid])
{
cout<<mid<<endl;
exit(0);
}
else if(key>a[mid])
bot=mid+1;
else
top=mid-1;
}
cout<<-1<<endl;
}
int main()
{
freopen("half.in","r",stdin);
freopen("half.out,"w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>key;
if(key<a[1] || key>a[n])
cout<<-1<<endl;
else
Half();
return 0;
}