7、递归的二分查找

  1 #include<iostream>
  2 
  3 using namespace std;
  4 //迭代二分查找
  5 int BinarySearch_I(int *a,const int x,const int n);
  6 //递归二分查找
  7 int BinarySearch_R(int *a,const int x,const int left,const int right);
  8 int main()
  9 {
 10 	int m[]={1,2,3,4,5,6,7,8,9,10};
 11 	int result;
 12 	int num=7;//要查找的数
 13 	if((result=BinarySearch_I(m,num,9))<0)
 14 	{ cout<<"迭代算法：没找到！"<<endl;}
 15 	else {
 16 		cout<<"迭代算法：在m["<<result<<"]处找到"<<num<<endl;
 17 	}
 18 
 19 
 20 	if((result=BinarySearch_R(m,num,0,9))<0)
 21 	{ cout<<"递归算法：没找到！"<<endl;}
 22 	else {
 23 		cout<<"递归算法：在m["<<result<<"]处找到"<<num<<endl;
 24 	}
 25 	system("pause");
 26 	return 0;
 27 }
 28 int BinarySearch_I(int *a,const int x,const int n)
 29 {
 30 	int left=0,right=n-1;
 31 	while(left<=right)
 32 	{
 33 		int middle = (left+right)/2;
 34 		if(x<a[middle]) right = middle-1;
 35 		else if(x>a[middle]) left=middle+1;
 36 		else return middle;
 37 	}
 38 	return -1;
 39 }
 40 int BinarySearch_R(int *a,const int x,const int left,const int right)
 41 {
 42 	if(left<=right)
 43 	{
 44 		int middle=(left+right)/2;
 45 		if(x<a[middle]) return BinarySearch_R(a,x,left,middle-1);
 46 		else if(x>a[middle]) return BinarySearch_R(a,x,middle+1,right);
 47 		else return middle;
 48 	}
 49 	return -1;
 50 }
 51 
 52