二分模板

RainbowQAQ · 2023-10-22 21:39:32 · 个人记录

1. 找到第一个大于等于 x 的数

#include <bits/stdc++.h>

using namespace std;

int n, a[100], x;

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    cout << l << " " << a[l] << endl;
    return 0;
}

2. 找到第一个大于 x 的数

#include <bits/stdc++.h>

using namespace std;

int n, a[100], x;

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] > x) r = mid;
        else l = mid + 1;
    }
    cout << l << " " << a[l] << endl;
    return 0;
}

3. 找到最后一个小于等于 x 的数

#include <bits/stdc++.h>

using namespace std;

int n, a[100], x;

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

4. 找到最后一个小于 x 的数

#include <bits/stdc++.h>

using namespace std;

int n, a[100], x;

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

5. 实数二分向下取整

#include <bits/stdc++.h>

using namespace std;

// 找精确到六位的eps
const double eps = 1e-8;

int main() {
    double l = 0, r = 1e5;
    double x; cin >> x;
    while (r - l >= eps) {
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

6. 实数二分向上取整

#include <bits/stdc++.h>

using namespace std;

// 找精确到六位的eps
const double eps = 1e-8;

int main() {
    double l = 0, r = 1e5;
    double x; cin >> x;
    while (r - l >= eps) {
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", r);
    return 0;
}