AcWing算法基础课---第一讲基础算法---02二分

整数二分模板

l = mid这个模板mid需要+1

int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
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;
else r = mid - 1;
}
return l;
}

浮点数二分

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

AcWing 790. 数的三次方跟

注意二分范围不是0到x因为当x小于1，三次方根会大于1

#include <iostream>

using namespace std;

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

AcWing 789. 数的范围

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int 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;
            
        }
        
    }
    return 0;
}