二分

• 【整数二分】起止位置
• 【小数二分】求算术平方根
• 【二分答案】切割绳子

二分本质
给定一个具有单调性的区间 \([l,r]\)，中间切一刀 \(mid=(l+r)/2;\) 可以将区间分为两个子区间，其合法的答案一定在其中的一个子区间中，继续对该区间进行二分。

按照上述原理，有一个问题：\(mid\) 这个位置分给左右那个区间？
（1）分给左区间，相当于：\([l,r] = [l,mid] + [mid+1,r]\); // 找右边界
（2）分给右区间，相当于：\([l,r] = [l,mid-1] + [mid,r]\); // 找左边界

【整数二分】起止位置

有 n 位同学按照年龄从小到大排好队。
王老师想要进行 q 次查询，年龄为 x 的同学，在队伍中首次出现的位置和最后一次出现的位置；如果队伍中不存在年龄为 x 的同学，请输出 -1。

输入格式：
第一行包含整数 n 和 q，表示队伍中的总人数和询问个数。
第二行包含 n 个整数（均在1~10000范围内），表示队伍中每个人的年龄。
接下来 q 行，每行包含一个整数x，表示一次询问的值。

输出格式：
共 q 行，每行包含两个整数，表示所求年龄在队伍中的起始位置和终止位置。
如果数组中不存在该元素，则返回"-1 -1"。

数据范围： 1≤n≤100000, 1≤q, x≤10000。

6 3
1 2 2 2 3 3
2
1
8

2 4
1 1
-1 -1

分析： 单次询问要做到 \(log_2n\) 级别，考虑二分查找左右边界。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x,a[N];
// 求 x 出现的右边界, [l,r] = [l,mid] + [mid+1,r]
int lower(int l,int r, int x) { 
    while(l<r) {
        int mid=l+r>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    if(a[l]!=x) l=-1; return l;
}
// 求 x 出现的左边界, [l,r] = [l,mid-1] + [mid,r]
int upper(int l,int r,int x) {
    while(l<r) {
        int mid=l+r+1 >>1;
        if(a[mid]<=x) l=mid;
        else r=mid-1;
    }
    if(a[l]!=x) l=-1; return l;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    while(m--) {
        cin>>x;
        cout<<lower(1,n,x)<<" "<<upper(1,n,x)<<endl;
    }
    return 0;
}

【小数二分】求算术平方根

给定 n，求 \(\sqrt{n}\)，保留小数点后 6 位。

3.14

1.772005

• 牛顿迭代

• 小数二分

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
double sqr1(double n) { // 牛顿迭代
    double a=n;
    while(abs(a-n/a) > eps) {
        a = (a+n/a) / 2;
    }
    return a;
}
double sqr2(double n) { // 小数二分
    double l=0, r=n;
//    while(r-l > eps){  // 写法 1
    for(int i=1; i<=100; i++) { // 写法 2：直接枚举100次
        double mid = (l+r)/2;
        if(mid*mid >= n) r=mid;
        else l=mid;
    }
    return l;
}
int main() {
    double n=3.14;
    printf("%.6lf\n", sqrt(n));
    printf("%.6lf\n", sqr1(n));
    printf("%.6lf\n", sqr2(n));
}

【二分答案】切割绳子

有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。

输入格式：
第一行是一个不超过 100 的正整数 n。
第二行是 n 个不超过 \(10^6\) 的正整数，表示每条绳子的长度。
第三行是一个不超过 \(10^8\) 的正整数 m。

输出格式:
绳段的最大长度，若无法切割，输出“Failed”。

3
5 10 8
2

8

参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n,m,a[N];
// 检查 绳段的最大长度在 >= x 的情况下能否切割出至少 m 条绳子。
bool chk(int x){
    int s=0;
    for(int i=1; i<=n; i++) s += a[i]/x;
    return s >= m;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    int l=1, r=1e6;
    while(l < r){
        int mid = l+r+1 >> 1;
        if(chk(mid)) l=mid;
        else r=mid-1;
    }
    if(chk(l)) cout<<l;
    else cout<<"Failed";
    return 0;
}