【模板】二分答案（3个）

发表于 | 分类于 | 本文总阅读量 次
字数统计: 263 字 | 阅读时长 ≈ 1 分钟

其实二分答案思路很简单。。。本不应该有这篇文章的，可是在做题的时候发现还是有一些细节，时间长了容易忘记，所以还是写了这篇文章，方便后续查找。

整数二分

求较大区间的最小临界值

1
2
3
4
5
6
7
8
9
10
11
12
13
while (l < r)
{
    int mid = (l + r) / 2;
    if (check(mid))
    {
        r = mid;
    }
    else
    {
        l = mid + 1;
    }
}
int ans = l;

求较小区间的最大临界值

1
2
3
4
5
6
7
8
9
10
11
12
13
while (l < r)
{
    int mid = (l + r + 1) / 2;
    if (check(mid))
    {
        l = mid;
    }
    else
    {
        r = mid - 1;
    }
}
int ans = l;

浮点二分

1
2
3
4
5
6
7
8
9
10
11
12
13
while (fabs(r - l) > eps)
{
    double mid = (l + r) / 2;
    if (check(mid))
    {
        r = mid;
    }
    else
    {
        l = mid;
    }
}
int ans = l;

主要的要点就是在整数二分的时候，都是令else的部分多加一个或者多减一个（至于是l还是r、加还是减可以通过语义判断），如果是下半区间的话，计算mid时需要上取整。

浮点二分基本上随便写了，注意用精度比较即可。