引入

首先我们来做一个游戏

请在一个范围内取一个数x

询问者每次询问一个数,若x等于该数则结束

若x大于该数就说大

若x小于该数就说小

很简单的规则,让我们来看看怎么操作

法一:直接枚举,从1问到x

但是sei还这么做啊~

法二:每次问答案可能存在区间的一半位置,缩小答案范围,直到找到答案

这就是二分答案

模板

那么接下来我们用代码的方式实现上述操作

直接枚举:

#include<bits/stdc++.h>

using namespace std;

int main() {
    int x;
    cin >> x;

    int cnt = 0;
    int l = 1, r = 1000;
    for (int i = l; i <= r; i++) {
        cnt++;
        if (i == x) {
            cout << x << endl;
            break;
        }
    }
    cout << "Guess times:" << cnt << endl;

    return 0;
}

二分答案:

#include<bits/stdc++.h>

using namespace std;

int main() {
    int x;
    cin >> x;

    int cnt = 0;
    int l = 1, r = 1000;
    while (l < r) {
        cnt++;
        int mid = (l + r) / 2;
        cout << endl;
        cout << "range:" << l << "~" << r << endl;
        cout << "mid value:" << mid << endl;
        if (x <= mid) {
            r = mid;
            cout << "Left" << endl;
        } else {
            l = mid + 1;
            cout << "Right" << endl;
        }
    }
    cout << l << endl;
    cout << "Guess times:" << cnt << endl;

    return 0;
}

那么这样就能大幅度减少求出答案所需的时间

二分答案,首先需要确定答案的范围

其次,要判定一个数与答案的大小关系

最后,要确定输出的答案是什么

int l = 1, r = 1000;
while (l < r) {
    int mid = (l + r) >> 1;
    //这里要用>>,为了处理负数情况
    
    //如果Check(mid)返回true,说明答案<=mid
    if (Check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

如上,只要实现Check函数就可以了

模板题

例2

1242 网线主管

#include<bits/stdc++.h>

using namespace std;

int n, K;
int a[10010];

bool Check(int L) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i] / L;
    }
    return sum >= K;
}

int main() {
    cin >> n >> K;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        double d;
        cin >> d;
        a[i] = 100 * d;
        mx = max(mx, a[i]);
    }

    int l = 0, r = mx;
    while (l < r) {
        int mid = ((l + r) >> 1) + 1;
        if (Check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    int ans = l;
    if (ans < 1) {
        printf("0.00");
    } else printf("%.2f", ans / 100.0);

    return 0;
}

例3

1243 月度开销

如果在题目中看到了最大的最小或最小的最大这样的字眼,就可以考虑二分答案

#include<bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];

bool Check(int x) {
    int money = 0, month = 1;
    for (int i = 1; i <= n; i++) {
        if (money + a[i] > x) {
            money = a[i];
            month++;
        } else {
            money += a[i];
        }
    }
    return month <= m;
}

int main() {
    int sum = 0;
    int mx = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }

    int l = mx, r = sum;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (Check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}

课后习题

1247 河中跳房子

1433 愤怒的牛

1434 Best Cow Fences