整数二分

具有单调性的一组数据,可以通过二分法求得边界。

往往使用二分求最小的最大值或最大的最小值。

下面的写法保证答案处于[l, r]之间,循环以l=r结束。

  • 写法一(在单调序列a中查找>=x的数中最小的一个):
1
2
3
4
5
6
7
8
while(l < r)
{
int mid = l + r;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}

return a[l];
  • 写法二(在单调序列a中查找<=x的数中最大第一个):
1
2
3
4
5
6
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}

第二种写法之所以加1,是避免r-l=1时,由于向下取整出现死循环的问题。

实数二分

实数二分无需考虑边界问题,每一步均可使l=mid,r=mid。

仅仅需要注意精度问题,如需保留k位小数,精度取$10^{-(k+2)}$。

1
2
3
4
5
6
while(r - l > 1e-5)
{
double mid = (l + r) / 2;
if(calc(mid)) r = mid;
else l = mid;
}

有时候精度不确定或不好表示,也可以使用循环,这样结果更准确。

1
2
3
4
5
6
for(int i = 0; i < 100; i++)
{
double mid = (l + r) / 2;
if(calc(mid)) r = mid;
else l = mid;
}