//二分查找
#include<iostream>
const int MAXN=10010;
using namespace std;
//二分查找,递归实现
int binarySearch(int a[],int low,int high,int key)
{
//查找某元素是否在数组中,若存在,则返回下标,否则返回-1;
int mid=(low+high)/2;
if(low>high){
return -1;//该元素不在数组中
}
if(a[mid]==key)
return mid;
else if(a[mid]>key)
return binarySearch(a,low,mid-1,key);
else
return binarySearch(a,mid+1,high,key);
return -1;//该元素不在数组中
}
//二分查找,迭代实现
int binarySearch2(int a[],int low,int high,int key)
{
//查找某元素是否在数组中,若存在,则返回下标,否则返回-1;
if(low>high){
return -1;//该元素不在数组中
}
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
else if(a[mid]>key)
high=mid-1;
else
low=mid+1;
}
return -1;//该元素不在数组中
}
int main()
{
int n,i;
int num,a[MAXN];
int find=0;//查找标志
cout<<"二分查找法,请输入数列个数\n";
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
while(true)
{
cout<<"\n请输入要查找的数:"<<endl;
cin>>num;//读入要查找的数
//find=binarySearch(a,0,n-1,num);
find=binarySearch2(a,0,n-1,num);
if(find==-1)
cout<<"抱歉!查无此数\n";
else
cout<<"恭喜你,查找成功!数列第"<<find+1<<"个\n";
}
return 0;
}