牛骨文教育服务平台(让学习变的简单)

STL经典算法集锦<五>之查找(lower_bound/upper_bound/binary_search)

这三个算法都比较的常用,而且具有一定的相似的性。理论依据也很明显,下面就直接贴出自己的实现版本。其中lower_bound与upper_bound实现了两个版本。版本一与STL的实现方法完全相同,以数据的总长度折半,版本二则是直接取前后的中点。当然本质上没有太大区别。

lower_bound版本一:

int lowerBound(int array[],int left,int right,int value)
{
		int mid=0,half=0;
		int len=(right+left+1)/2;
		while(len>0)
		{
				half=len>>1;          //数据长度折半
				mid=left+half;        //计算中点
				if (array[mid]<value) //调整总长与起点
				{
						len=len-half-1;
						left=mid+1;
				}
				else
						len=half;
		}
		return left;
}

lower_bound版本二:

int lowerBound(int array[],int left,int right,int value)
{
		int mid=0;
		while(left<right)
		{
				mid=(right+left)/2;       //计算中点
				if (array[mid]<value)     //调整起点或者终点
						left=mid+1;
				else
						right=mid;
		}
		return right;
}

upper_bound版本一:

int upperBound(int array[],int left,int right,int value)
{
		int mid=0,half=0;
		int len=(right+left+1)/2;
		while(len>0)
		{
				half=len>>1;         //长度折半
				mid=left+half;       //计算中点
				if (array[mid]>value) //调整长度与起点
						len=half;
				else
				{
						len=len-half-1;
						left=mid+1;
			}
		}
		return left;
}

upper_bound版本二:

int upperBound(int array[],int left,int right,int value)
{
		int mid=0;
		while(left<right)
		{
				mid=(right+left)/2;    //计算中点
				if (array[mid]>value)  //调整起点或者终点
						right=mid;
				else
						left=mid+1;
		}
		return right;
}

折半查找:

int binarySearch(int array[],int left,int right,int value)
{
		int mid;
		while(left<=right)
		{
				mid=(left&right)+((left^right)>>1);      //防止溢出
				if(array[mid]==value)
						return mid;
				else if (array[mid]<value)
						left=mid+1;
				else
						right=mid-1;
		}
		return -1;
}

可用测试代码:

int main()
{
		srand(time(0));
		int len=21;
		int array[len];
		for(int i=0;i<len;i++)
				array[i]=rand()%200;
		sort(array,array+len);
		for(int i=0;i<len;i++)
				cout<<array[i]<<"	";
		cout<<endl;
		cout<<"
result:"<<binarySearch(array,0,len-1,33)<<endl;
		return 0;
}