二分查找算法的几种实现

最简单的二分

1.循环实现

template <typename T>
int binary_search(const vector<T> &set, const T &value)
{
	auto low = set.begin();
	auto high = set.end();
	auto high_dump = high;
	auto low_dump = low;

	auto mid = low + ((high - low) >> 1);
    /*1.　mid=(low+high)/2,如果　low　和　high　太大就会产生溢出*/
	while ((low <= high) && (mid != high_dump))   /*2.　一定是 <= */
	{
		if (*mid == value)
			return mid - low_dump;
	      /*3.　一定要+1，-1，不然当　low　=　high时，就会产生死循环*/
		if (*mid < value)
			low = mid + 1;
		else
			high = mid - 1;
		mid = low + ((high - low) >> 1);
	}
	return -1;
}

2. 递归实现

template <typename ForwardIt, class T>
bool binary_search(ForwardIt frist, ForwardIt last, const T &value)
{
	if (frist > last)
		return false;
	auto mid = frist + ((last - frist) >> 1);
	if (*mid == value)
		return true;
	if (*mid < value)
		binary_search(mid + 1, last, value);
	else
		binary_search(frist, mid - 1, value);
}

几种变式

1.查找第一个值等于给定值的元素

/*  1.查找第一个值等于给定值的元素
[1,3,4,5,6,8,8,8,11,18]
找到返回下标，找不到返回　－1　*/

template <typename ForwardIt, class T>
int binary_search(ForwardIt low, ForwardIt high, const T &value)
{
	auto low_dump = low;
	auto high_dump = high ;
	auto mid = low + ((high - low) >> 1);
	while  ((low <= high) && (mid != high_dump))
	{
		if (*mid < value)
			low = mid + 1;
		else if (*mid > value)
			high = mid - 1;
		else
		{
			if ((mid == low_dump) || (*(mid - 1) != value))
				return mid - low_dump;
			else
				high = mid - 1;　　/*缩进high的距离*/
		}
		mid = low + ((high - low) >> 1);
	}
	return -1;
}

2.查找最后一个值等于给定值的元素

同上

3. 查找第一个大于等于给定值的元素

/*3.查找第一个大于等于给定值的元素
[1,3,4,5,6,8,8,8,11,18]
找到返回下标，找不到返回 -1
*/
template <typename ForwardIt, class T>
int binary_search(ForwardIt low, ForwardIt high, const T &value)
{
	auto low_dump = low;
	auto high_dump = high;
	auto mid = low + ((high - low) >> 1);
	while ((low <= high) && (mid != high_dump))
	{
		if (*mid < value)
			low = mid + 1;
		else if (*mid >= value)
		{
			if ((mid == low_dump) || (*(mid - 1) < value))
				return mid - low_dump;
			else
				high = mid - 1;
		}
		mid = low + ((high - low) >> 1);
	}
	return -1;
}

4. 查找最后一个小于等于给定值的元素

/*4. 查找最后一个小于等于给定值的元素
[1,3,4,5,6,8,8,8,11,18]
找到返回下标，找不到返回 -1
*/
template <typename ForwardIt, class T>
int binary_search(ForwardIt low, ForwardIt high, const T &value)
{
	auto low_dump = low;
	auto high_dump = high;
	auto mid = low + ((high - low) >> 1);
	while ((low <= high) && (mid != high_dump))
	{
		if (*mid <= value)
		{
			if ((mid == high_dump - 1) || (*(mid + 1) > value))
				return mid - low_dump;
			else
				low = mid + 1;
		}
		else if (*mid > value)
			high = mid - 1;
		mid = low + ((high - low) >> 1);
	}
	return -1;
}