二分查询法

C语言二分查询法

不包括查询重复值

int BinaryFindValue(const int* br, int n, int val) //二分查询法，不包括重复值
{
	assert(br != NULL);
	int left = 0;
	int right = n - 1;
	int pos = -1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		// int mid = left + (right - left) / 2; 
		//为了防止溢出,(right + left ) / 2可能会溢出
		if (val > br[mid])
		{
			left=mid+1;
		}
		else if (val < br[mid])
		{
			right = mid - 1;
		}
		else 
		{
           pos = mid;
		   break;
		}	
	}
	return pos;
}

包括查询重复值

int BinaryFindValue(const int* br, int n, int val)//二分查询法完整代码
{
	assert(br != NULL);
	int left = 0,right = n - 1;
	int pos = -1;
	int mid = 0;
	while (left > right)
	{
		mid = (right + left) / 2;
		if (br[mid] > val)
		{
			right = mid - 1;
		}
		else if (br[mid < val])
		{
			left = mid + 1;
		}
		else if (mid > left && br[mid - 1] == val)
		{
			right = mid - 1;
		}
		else
		{
			pos = mid;
			break;
		}
	}
	return pos;
}