折半查找和递归折半查找详解（二分法查找，递归二分法查找）

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。（前提）

主要思想是：（设查找的数组区间为array[low, high]）

（1）确定该区间的中间位置K

（2）将查找的值T与array[k]比较。

若相等，查找成功返回此位置k；

否则确定新的查找区域，继续二分查找。

区域确定如下：

a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]

b.array[k]<T 类似上面查找区间为array[k+1,……，high]。

每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。

递归找，即可，时间复杂度:O(log2n)。

(A). 非递归方法的C++程序描述如下：

int BinarySearch(int *p,const int x,const int n)
{
	int left=0,right=n-1;

	while(left<=right)
	{
		int middle=(left+right)/2;
		if(x<p[middle])
		{
			right=middle-1;
		}
		else if(x>p[middle])
		{
			left=middle+1;
		}
		else
		{
			return middle;
		}

	}
		return -1;
}

完整的C++程序如下：

#include<iostream> 
using namespace std;
int BinarySearch(int *p,const int x,const int n)
{
	int left=0,right=n-1;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(x<p[middle])
		{
			right=middle-1;
		}
		else if(x>p[middle])
		{
			left=middle+1;
		}
		else
		{
			return middle;
		}
	}
	return -1;
}

int main()
{
	int a[5]={1,2,3,4,5};
	int y=5;
	int ret=BinarySearch(a,y,5);
	if(-1==ret)
	{
		cout<<y<<" 不存在！"<<endl;
	}
	else
	{
		cout<<y<<"的下标是： "<<ret<<endl;
	}
	return 0;
}

运行截图：

(B).  递归二分法查找C++程序描述如下：

<span style="color:#333333;">int BinarySearch(int *p,const int x,const int left,const int right)
{
	if(left<=right) 
	{
		int middle=(left+right)/2;
		if(x<p[middle])
		{
			return BinarySearch(p,x,left,middle-1);
		}
		else if(x>p[middle])
		{
			return BinarySearch(p,x,middle+1,right);
		}
		return middle;
	}
	return -1;	//没找到 
}</span>

完整的C++程序如下：

#include<iostream> 
using namespace std;
int BinarySearch(int *p,const int x,const int left,const int right)
{
	if(left<=right) 
	{
		int middle=(left+right)/2;
		if(x<p[middle])
		{
			return BinarySearch(p,x,left,middle-1);
		}
		else if(x>p[middle])
		{
			return BinarySearch(p,x,middle+1,right);
		}
		return middle;
	}
	return -1;	//没找到 
}
int main()
{
	int a[5]={1,2,3,4,5};
	int y=2;
	int ret=BinarySearch(a,y,0,4);
	if(-1==ret)
	{
		cout<<y<<" 不存在！"<<endl;
	}
	else
	{
		cout<<y<<"的下标是： "<<ret<<endl;
	}
	return 0;
}

运行截图如下：