整数二分

整数二分的本质并不是单调性。本质是将区间一分为二，寻找边界点（左区间边界还是右区间边界）。

每次缩短区间一半，答案依旧在缩短的区间内，直到区间长度为1，此时就是边界点。

二分一定是有解的，此时 l==r，根据二分出来的边界点判断题目有没有解

左区间边界点

• 取中点mid = l+r+1 >> 1，判断该点是否符合左区间性质
  • 如果成立说明mid在左区间，边界点在 [mid,r]，此时 l = mid
  • 不成立说明mid不在左区间，边界点在 [l,mid-1]，此时 r = mid-1

右区间边界点

• 取中点mid = l+r >> 1，判断该点是否符合右区间性质
  • 如果成立说明mid在右区间，边界点在 [l,mid]，此时 r = mid
  • 不成立说明mid不在左区间，边界点在 [mid+1,r]，此时 l = mid+1

mid分子加1

• 性质成立条件中：l = mid ，加1；r = mid ，不加1

不加 1，当 l = r - 1 时，由于向下取整，mid = l，当性质条件成立， l = mid = l 死循环。加1后，mid = r，不会死循环。

789 ?

789. 数的范围 - AcWing题库

左区间边界点与右区间边界点都涉及

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int q[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    while (m--) {
        int k;
        cin >> k;
        // ^ 寻找右区间边界点
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] >= k)
                r = mid;
            else
                l = mid + 1;
        }
        if (q[l] != k) {
            cout << "-1 -1" << endl;
            continue;
        } else
            cout << l << " ";
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] <= k)
                l = mid;
            else
                r = mid - 1;
        }
        cout << r << endl;
    }
    return 0;
}

浮点数二分

浮点数没有整除向下取整，可以精准一分为二，不需要处理边界。处理精度问题，加上经验值2，多处理两位小数。

// while(r-l >= 1e-8)
for (int i = 0; i < 100; i++) {
    double mid = (l + r) / 2;
    if (mid * mid * mid >= x)
        r = mid;
    else
        l = mid;
}

790 ?

790. 数的三次方根 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    double x;
    cin >> x;
    double l = 0, r = x;
    if (x < -1)  // 负数时调换两者位置
        l = x, r = 0;
    else if (x > -1 && x < 1)  // 小数时范围是 [-1,1]
        l = -1, r = 1;

    // while(r-l >= 1e-8)
    for (int i = 0; i < 100; i++) { // 区间长度 / (1 << 100) 
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%lf\n", l);
    return 0;
}

ANTI WEB SPIDER BOT www.cnblogs.com/linxiaoxu

高精度（整数运算）

大整数位数 1e6 ，小整数值 <= 1e9 。（python、java自带大整数类型）

A + B

791. 高精度加法 - AcWing题库

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

// 加引用符不用拷贝一遍效率更高
vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

A - B

792. 高精度减法 - AcWing题库

要保证 A >= B，如果B大，则算 -(B - A) ；如果 A、B 有负数，可以转换成 |A| - |B| 或 |A| + |B|。