二分 | AHaiTang's Blog

二分的模板

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//模板一
int bsearch1(int l, int r){
    while (l < r){
        int mid = (l + r ) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1  ;
    }
    return l;
}

// 对于很大的数据,l+r 可能会溢出，可写成 l+(r-1>>1) 

// 模板二
int bsearch2(int l, int r) {
    while (l < r){
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid;
        else r = mid -l;
    }
    return r;
}

// 模板三（掌握）
int bsearch3(int l,int r) { 
    int ans = 0;
    while(l <= r) {
        int mid = (l+r) / 2;
        if(check(mid) ) {  ans = mid; l = mid + 1;}
        else r = mid - 1;
    }
    return ans; 
}

// 浮点二分
double bsearch4(double l, double r)  {
    const double eps = 1e-6;  
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;    // check()判断mid是否满足性质
        else r = mid - 1;          // 如果mid不满足性质，则将其从搜索区间中去除     
    }
}

第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。
只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一；
只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一；

例题

最大值最小，最小值最大类问题解题方向：
最短距离最大化问题：保证任意区间距离要比最短距离mid大或相等（这样，mid才是最短距离）即：区间的距离>=mid
最长距离最小化问题：保证任意区间距离要比最大距离mid小或相等（这样，mid才是最大距离）即：区间的距离<=mid

数的范围

 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
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    i64 n, q;
    cin >> n >> q;
    vector<i64> nums(n + 2, 0); 
    for(i64 i = 1; i <= n; i++) cin >> nums[i];
    nums[n + 1] = LLONG_MAX;
    
    while(q--) {
        i64 num;
        cin >> num;
        i64 l = 1, r = n + 1;
        while(l < r) {
            i64 mid = (l + r) / 2;
            if(num <= nums[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        i64 first_pos = l;
        if(first_pos > n || nums[first_pos] != num) {
            cout << "-1 -1\n";
            continue;
        }
        l = 1, r = n + 1;
        while(l < r) {
            i64 mid = (l + r + 1) / 2;
            if(num >= nums[mid]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        i64 last_pos = l;
        cout << first_pos - 1 << " " << last_pos - 1 << "\n";
    }
}

int main() {
    solve();
    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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
// using u128 = unsigned __int128;

using pii = pair<i32, i32>;
using pll = pair<i64, i64>;

i64 MAX = numeric_limits<i64>::min();
i64 MIN = numeric_limits<i64>::max();
i64 M = 1e9 + 7;

// 定义 (通过反余弦函数计算)
const double PI = acos(-1.0);
// 定义一个极小误差值，用于浮点数比较
const double eps = 1e-9;

void solve() {
    double n;
    cin >> n;
    double l = -1e2, r =  1e2;
    int t = 0;
    while(r - l > eps) {
        t++;
        double mid = (l + r) / 2;
        double temp = mid * mid * mid;
        if((n - temp) > eps) l = mid;
        else r = mid;
    }
    printf("%.6lf", l);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

二分的模板#

例题#

二分的模板

例题