【文件属性】:
文件名称:二分查找算法C++,递归和迭代
文件大小:1KB
文件格式:CPP
更新时间:2023-04-11 12:04:58
二分查找 递归 迭代
//二分查找
#include
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>a[i];
while(true)
{
cout<<"\n请输入要查找的数:"<>num;//读入要查找的数
//find=binarySearch(a,0,n-1,num);
find=binarySearch2(a,0,n-1,num);
if(find==-1)
cout<<"抱歉!查无此数\n";
else
cout<<"恭喜你,查找成功!数列第"<