二分查找算法的几种实现

最简单的二分

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;
}

例题：统计一个数字在排序数组中出现的次数。

class Solution
{
public:
    //1.查找第一个值等于给定值的元素
    int BinSearch(vector<int> data, int k)
    {
        int low = 0;
        int high = data.size() - 1;
        int mid = low + ((high - low) >> 1);
        while (low <= high)
        {
            if (data[mid] == k)
            {
                if (mid == 0 || data[mid - 1] != k)
                    return mid;
                else
                    high = mid - 1;
            }
            else if (data[mid] < k)
                low = mid + 1;
            else
                high = mid - 1;
            mid = low + ((high - low) >> 1);
        }
        return -1;
    }
    int GetNumberOfK(vector<int> data, int k)
    {
        if (data.size() <= 0)
            return 0;
        // 二分找到
        // 然后遍历
        int index = BinSearch(data, k);
        if (index < 0)
            return 0; //表示不存在
        int res = 0;
        for (auto it = data.begin() + index + 1; it != data.end(); it++)
        {
            if (*it == k)
                res++;
            else
                break;
        }
        return res + 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;
}