51:30 -> 1:13:30

基本思想

找划分不同区间的边界点

整数二分模版题：数的范围

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

#include <iostream>
using namespace std;

const int N = 100010;
int q[N];

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

浮点数二分模版题：

1:13:30 -> 结束

数的平方根

下面这个写法是有问题的，l取0，r取x，如果x是0.01，0.01的平方根是0.1
二分出来的结果值0.1，不在值域【0，0.01】中，所以就出现了问题
二分出的结果，一定要在值域范围内

#include <iostream>
using namespace std;

int main(){
    double x;scanf("%lf",&x);
    //*********************这里r取x有问题
    double l = 0 , r = x;
    //*********************
    while(r-l > 1e-8){
        double mid = (l + r)/2;
        if(mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf",l);
    return 0;
}

按照输入数据的范围设置l和r即可保证二分的结果仍在范围中

#include <iostream>
using namespace std;

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

数的三次方根

给定一个浮点数n，求它的三次方根。

输入格式

共一行，包含一个浮点数n。

输出格式

共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。

数据范围

−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

代码：

• l，r取给的数据范围，保证二分出来的结果，在l和r以内
• r-l > 1e-8 题目说了保留六位小数，所以这里是1e-8，精度要多两位 ```cpp

  include

  using namespace std;

int main(){ double x;scanf(“%lf”,&x); //l，r取给的数据范围，保证二分出来的结果，在l和r以内 double l = -10000 , r = 10000; // r-l > 1e-8 题目说了保留六位小数，所以这里是1e-8，精度要多两位 while(r-l > 1e-8){ double mid = (l + r)/2; if(mid mid mid >= x) r = mid; else l = mid; } printf(“%lf”,l); return 0; } ```