整数二分

一、整数二分性质

  • 确定一个区间，使得目标值一定在区间中。
  • 找到一个性质，其满足：①该性质具有二段性 ②答案是二段性的分界点 。

二、整数二分模板

L：左端点
R：右端点
M：区间中点
ans：答案

第一类：ans是红色区间的右端点

将$[L, R]$分成$[L, M-1]$和$[M, R]$，如果$M$是红色的，说明$ans$在$[M, R]$区间内；否则$M$是绿色的，说明$ans$在$[L, M-1]$区间内。

第二类：ans是绿色区间的左端点

将$[L, R]$分成$[L, M]$和$[M+1, R]$，如果$M$是绿色的，说明$ans$在$[L, M]$区间内；否则$M$是红色的，说明$ans$在$[M+1, R]$区间内。

三、关于M的取值

结论

当$L=M$，$R=M-1$，$M=L+R+1>>1$；当$R=M$，$L=M+1$，$M=L+R>>1$。

证明

第一种模板：设$M=L+R>>1$，$L=R-1$，那么$M=L$，当执行$L=M$时，$L=M=L$，$L$的值未改变，会发生死循环。

第一种模板：设$M=L+R+1>>1$，$L=R-1$，那么$M=R$，当执行$R=M$时，$R=M=R$，$R$的值未改变，会发生死循环。

四、整数二分步骤

  1. 找一个区间$[L, R]$，使得答案一定在该区间中。
  2. 找到一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
  3. 分析中点M在该判断条件下是否成立：如果成立，考虑在哪个区间；如果不成立，考虑在哪个区间。
  4. 如果更新方式为$R=M$，则不用做任何处理；如果更新方式是$L=M$，那么$M=L+R+1>>1$。

五、模板题

Acwing 789. 数的范围

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
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int q[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) 
        cin >> q[i];

    while (k--) {
        int x;
        cin >> x;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << " ";
            l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}