基础二分算法：整数二分、浮点二分-526互联

1、整数二分

以acwing 789为例，题目要求如下：

第一行输入整数n和q，表示数组长度和询问个数。

第二行输入数组，包含n个整数。

接下来q行，每一行一个整数k，表示一个问询元素。

要求输出q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m, q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while (m--) {
        int x;
        scanf("%d", &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 << ' ';

            //寻找最后一个满足条件的值
            int 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;
        }
    }
}

2、浮点二分

浮点二分需要确定精度，但不需要和整数二分一样做加1减1的边缘判断。

以求根号为例，

要求输入一个double值，返回其算术平方根，要求精度保留四位小数。

#include <iostream>
using namespace std;

int main() {
    double x;
    cin >> x;
    
    double l = 0, r = x;
    while (r - l > 1e-6) {
        double mid = (l + r) / 2; 
        if (mid * mid >= x) r = mid; 
        else l = mid;
    }

    printf("%lf", l);

    return 0;
}