整数二分

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

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

下面的写法保证答案处于[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;
}