二分法的应用-C++_c++分治二分法

二分法是典型的分治算法。

我们使用二分法通常的目的是为了减小遍历规模。假如求解一个问题，本来需要遍历整个数组，得到结果。但是由于数组的特殊性或问题的特殊性，我们能够排除一半的错误结果不需要遍历，这就是二分法的使用逻辑。

一般，二分法会把一个时间复杂度为O(n) 的算法缩减为复杂度O(log n)

下面使用二分法求解几个问题：

1、问题：在一个有序数组中，找某个指定数值是否存在。

解：要求解特定值，假设特定值为A。由于数组有序，我们可以先求数组的中间位置的值B，如果A>B,则说明A在B的右半侧，反正，A在左半侧。以此类推，可以找到数组中是否有A值

参考代码

bool MyFun(std::vector<int>& arr,const int A)
{
	int start = 0; //起始位置
	int end = arr.size()-1; //末尾位置
 
	if (A == arr[start] || A == arr[end])
	{
		return true;
	}
	//使用二分法求解
	while (start != end)
	{
		int mid = (start + end) / 2; //获取中间位置的数值
		//如果相等，则找到A
		if (A == arr[mid])
		{
			return true;
		}
		//如果A比较大，说明A在mid右侧
		else if(A > arr[mid])
		{
			if (start == mid)
			{
				break;
			}
			start = mid;
		}
		//如果A比较小，说明A在mid左侧
		else
		{
			if (end == mid)
			{
				break;
			}
			end = mid;
		}
	}
 
	return false;
}

2、问题：在一个有序数组中，找>=某个数最左侧的位置

解：首先，这个数组有序；其次，寻找某个特定的值（位置），这样很容易想到使用二分法。假设指定值为A，寻找>=A的最左侧，就是要尽量保留左半侧

int MyFun(std::vector<int>& arr,const int A)
{
	int start = 0; //起始位置
	int end = arr.size()-1; //末尾位置
	int ret = arr.size();
 
	if (arr[end] < A)
	{
		return ret;
	}
 
	if (arr[start] >= A)
	{
		return 0;
	}
 
	//使用二分法求解
	while (start != end)
	{
		int mid = (start + end) / 2; //获取中间位置的数值
		//如果mid位置>=A，则先记录mid，再丢弃右半部分，在左半侧继续寻找
		if (arr[mid] >= A)
		{
			ret = mid < ret ? mid : ret;
			if (end == mid)
			{
				break;
			}
			end = mid;
			//如果左半侧最大值小于A，则不需再找
			if (arr[end-1] < A)
			{
				break;
			}
		}
		//说明mid以左，都不存在不小于A的值，丢弃左半侧
		else
		{
			if (start == mid)
			{
				break;
			}
			start = mid;
			//如果左半侧最小值>=A，则不需再找
			if (arr[start+1] >= A)
			{
				ret = start + 1 < ret ? start + 1 : ret;
				break;
			}
		}
	}
 
	return ret;
}

【注】不一定需要有序的数组才能使用二分法求解，如果问题具有特殊性，无序数组也可以使用二分法。

例如：问题3

arr是一个无序数组，且相邻2个元素一定不相等。求这个数组的一个局部最小值。

参考代码

int MyFun(std::vector<int>& arr)
{
    int start = 0;
    int end = arr.size() - 1;
 
    //先查看第1个元素和最后一个元素是不是局部最小值
    if (arr[start] < arr[start + 1])
    {
        return arr[start];
    }
 
    if (arr[end] < arr[end - 1])
    {
        return arr[end];
    }
 
    //trend1为左侧的趋势；trend2为右侧的趋势；如果升序是true；降序是false
    //start和end的位置都不是局部最小所在位置，说明trend1是降序，trend2是升序
    bool trend1 = false;
    bool trend2 = true;
 
    //使用二分法求解
    while (start != end)
    {
        int mid = (start + end) / 2;
 
        //中间位置的趋势
        if (mid + 1 < end)
        {
            bool tr = arr[mid] < arr[mid + 1];
 
            if (trend1 == tr)
            {
                start = mid;
            }
            else if (trend2 == tr)
            {
                end = mid + 1;
            }
        }
        //不用继续比较，输出结果
        else
        {
            return arr[mid];
        }
    }
}