二分查找 复习

多在纸上演算！l 和 r 不要开出数组范围！

AcWing 789.数的范围

#include <iostream>

using namespace std;
const int N = 100010;

int n, q;
int a[N];

int bs1(int x) // 查找最左边值
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1; // 保持 mid 靠左
        if (a[mid] < x) l = mid + 1;
        else r = mid;
    }
    if (a[l] != x) return -1;
    return l;
}

int bs2(int x) // 查找最右边值
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1; // 保持 mid 靠右， 记得 + 1
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    if (a[l] != x) return -1;
    return l;
}

int main()
{
    cin >> n >> q;

    for (int i = 0; i < n; i++) cin >> a[i];

    while (q--)
    {
        int x; cin >> x;
        printf("%d %d\n", bs1(x), bs2(x));
    }

    return 0;
}

AcWing 790.数的三次方根

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
const double eps = 1e-10;

int main()
{
    double n; cin >> n;

    double mid, l = -10000, r = 10000; // 寻找三次方根
    while (l < r)
    {
        mid = (l + r) / 2;
        if (fabs(mid * mid * mid - n) < eps) break; // 找到
        else if (mid * mid * mid < n) l = mid;
        else r = mid;
    }

    printf("%.6lf\n", mid);

    return 0;
}