跳转至

二分

普通二分

计算中心点 \(m\) 的几种方法：

  • m = (l + r) >> 1
  • m = l + (r - l) >> 1
  • m = (l & r) + ((l ^ r) >> 1)

以下代码的二分区间为 \([l, r)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e3 + 9;
int d[MAXn];
int n, m;

bool check(int x) {
    // return true / false;
}

int ef() {
    int l = 0, r = 1e9 + 1;
    while(l + 1 < r) {
        int m = l + ((r - l) >> 1);
        if(check(m)) l = m;
        else r = m;
    }
    return l;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    scanf("%d", &m);
    int ans = ef();
    ans == 0 ? printf("Failed") : printf("%d", ans);
    return 0;
}

倍增

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e3 + 9;
int d[MAXn];
int n, m;

bool check(int x) {
    // return true / false;
}

int bz() {
    int ans = 0;
    for(int i = 20; i >= 0; i --) {
        int t = ans | (1 << i);
        if(check(t)) ans = t;
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    scanf("%d", &m);
    int ans = bz();
    ans == 0 ? printf("Failed") : printf("%d", ans);
    return 0;
}
小波与二分

摘录自 离散小波变换° 的 QQ 消息：

  • 哎呦，每次我写二分我都头疼
  • 一想到二分区间应该是左闭右开还是闭区间，(l+r)/2会不会触发向零取整，check完答案后到底应该设置为 mid 还是 mid+1，循环条件到底是 l<=r 还是 l<r 还是别的什么东西，我就开始爆炸了
  • 怎么办，学不会二分，这辈子算是完了
  • 你们学二分的是不是都能搞清楚二分
  • 主要是二分的等价写法太多了，但是混写就会出问题，很头大）
  • 有一个选手因为学不明白二分所以用了五年的倍增
  • 我写不来二分，其实主要是搞不清楚边界情况，非二分不可的情况我还是会仔细研究一下咋写）
  • 不过目前除了讲课之外还没碰到非二分不可的情况）