二分算法总结

关于二分算法想必大家也是耳熟能详,但是在实施算法时，往往在细节方面由于没有考虑周全而抓耳挠腮，百思不得其解。这很正常。因为当年在学术界，第一个正确的二分算法写出来就花了20年；又不正常。现在，对于二分算法无论是理论研究还是实际运用都已经很纯熟了，我们既然可以站在巨人的肩膀上，那又何乐而不为呢？
　　这里总结一下一些常用的二分算法的写法。

一、二分查找

查找序列为严格递增序列，元素所在区间为[0,n-1]。当元素存在重复时，它不保证返回序列中第一个该元素的索引，故待查找序列不应存在重复元素。

int binarySearch(int l, int r, int x)
{
	int mid;
	while(l <= r)			/* 若此时l==r，还要进行一次查找*/
	{						/* 当l>r时，查找失败，退出循环*/
		mid = (l + r) / 2;	/* 备注1 */
		if(s[mid] == x)		/* 返回元素所在序列的索引*/
			return mid;
		if(s[mid] > x)
			r = mid - 1;	/* 此时目标元素x存在区间为[l,mid - 1]*/
		else
			l = mid + 1;	/* 此时目标元素x存在区间为[mid + 1,r]*/
	}
	return -1;				/* 没有找到，返回-1*/
}

备注1：此处可能存在 l + r 溢出int范围，所以可以用 l + (r-l)/2避免溢出

二、解析STL中lower_bound和upper_bound

lower_bound(求序列中第一个大于等于目标元素x的索引)

查找序列为非递减序列，初始区间为[1,n]——(因为x可能大于序列中所有的元素，此时满足条件的元素就是其本身，此时返回值为n)，

int lower_bound(int l, int r, int x)
{
	int mid;
	while(l < r)			/* 当l==r时，该位置唯一，循环结束*/
	{
		mid = l + (r - l) / 2;
		if(s[mid] >= x)		/* 第一个大于等于x的索引在[l, mid]里 */
			r = mid;
		else
			l = mid + 1;	/* 第一个大于等于x的索引在[mid+1, r]里 */
	}
	return l;
}

upper_bound(求序列中第一个大于目标元素x的索引)

查找序列为非递减序列，代码与与上面类似。

int lower_bound(int l, int r, int x)
{
	int mid;
	while(l < r)			/* 当l==r时，该位置唯一，即是目标位置，循环结束*/
	{
		mid = l + (r - l) / 2;
		if(s[mid] > x)		/* 第一个大于x的索引在[l, mid]里 */
			r = mid;
		else
			l = mid + 1;	/* 第一个大于x的索引在[mid+1, r]里 */
	}
	return l;
}

三、二分思想运用

看一道经典题:

给出N个线段长度，试将它们头尾相接组合成一个凸多边形，使凸多边形的外接圆（多边形每个顶点都在圆上）的半径最大，求该最大半径。其中N<=10^5，线段长度均不超过100，要求算法中不涉及坐标的计算。

分析:

思路1

首先，因为圆心不确定，想涉及坐标计算也无能为力啊????。
其次，考验数学时候来啦。我们可以确定当圆是凸多边形外接圆时，该多边形内角和为$π*(n-2)$π∗(n−2)，对于每一条弦（题中线段），与两条半径组成等腰三角形，解该等腰三角形其底角为
$α_{i}=arccos(\frac{s_{i}/2}{r})$αi​=arccos(rsi​/2​)
则凸多边形内角和为$\sum_{i=0}^{n-1}α_{i}$∑i=0n−1​αi​。此时则可以二分$r$r，当内角和小于误差限时，即得到最大半径。

思路2

换一个角度，一条线段(弦)对应的圆心角为
$α_{i}=arcsin(\frac{s_{i}/2}{r})$αi​=arcsin(rsi​/2​)
而当r确定，所有的弦对应的圆心角和$\sum_{i=0}^{n-1}α_{i}=2π$∑i=0n−1​αi​=2π，此时可以二分$r$r，当内角和小于误差限时，即得到最大半径。
思路1和2，C++代码链接：二分思想题解