天天看點

C++ 二分查找的遞歸與非遞歸實作

非常簡單的東西,直接看看代碼。

/*二分查找的遞歸與非遞歸實作*/
#include <iostream>
using namespace std;
//設定為非重複的遞增整數列:循環方法
int BinarySearch(int array[],int value,int length)
{
	if(array == NULL || length < 1)
		return -1;
	int lp = 0;
	int rp = length -1;
	while(rp > lp)
	{
		int mid = (lp + rp)/ 2;
		if(array[mid] == value)
			return mid;
		if(array[mid] > value)
			rp = mid -1;
		else
			lp = mid +1;
	}
}
//遞歸方法
int binarySearch(const int array[],int value,int lp, int rp)
{
	if(array == NULL||lp > rp)
		return -1;
	int mid = (lp + rp)/2;
	if(array[mid] == value)
		return mid;
	else
	{
		if(array[mid] > value)
			binarySearch(array,value,lp,mid-1);
		else
			binarySearch(array,value,mid+1,rp);
	}
}
int main()
{
	const int length = 10;
	int a[length] = {1,2,3,4,5,6,7,8,9,100};
	cout <<"the loop result is: "<<BinarySearch(a,100,length)<<endl;
	cout <<"the recursion result is: "<<binarySearch(a,100,0,length-1)<<endl;
	system("PAUSE");
	return 0;
}
           

繼續閱讀