二分搜索非递归和递归算法

二分搜索非递归和递归算法

//二分搜索的非递归实现算法
//a为排好序的数组，x为要查找的值，n为数组中数字个数
int binary_Search(int *a,int x,int n)
{
int left = 0;
int right = n-1;
while(left<=right)
    {
int middle = (left+right)/2;
if(x==a[middle])return middle;
if(x>a[middle])left = middle+1;
else right = middle-1;
    }
return -1;
}
int main()
{
cout<<"请输入已排好序的数字个数"<<endl;
int n;cin>>n;
int a[n];
cout<<"请输入排好序的数字"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"请输入要搜索的数字"<<endl;
int x;cin>>x;
if(binary_Search(a,x,n)!=-1)
cout<<"搜索数字所在下标为: "<<binary_Search(a,x,n)<<endl;
else
cout<<"该搜索数字不存在"<<endl;
}

//二分搜索的递归实现算法
//Array为排好序的数组，key为要查找的值，low=0,high为数组中数字个数
int BinSearch(int Array[],int low,int high,int key)
{
if (low<=high)
    {
int mid = (low+high)/2;
if(key == Array[mid])
return mid;
else if(key<Array[mid])
return BinSearch(Array,low,mid-1,key);
else if(key>Array[mid])
return BinSearch(Array,mid+1,high,key);
    }
else
return -1;
}
int main()
{
cout<<"请输入已排好序的数字个数"<<endl;
int n;cin>>n;
int a[n];
cout<<"请输入排好序的数字"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"请输入要搜索的数字"<<endl;
int x;cin>>x;
if(BinSearch(a,0,n,x)!=-1)
cout<<"搜索数字所在下标为: "<<BinSearch(a,0,n,x)<<endl;
else
cout<<"该搜索数字不存在"<<endl;
}