AcWing算法基础课学习笔记第一讲基础算法 2. 二分

叁歲伎倆 2024-03-16 11:53 6阅读 0赞

### AcWing算法基础课学习笔记 ###

#### 文章目录 ####

*   *  AcWing算法基础课学习笔记
     *   *   *  第一讲 基础算法
             *   *  2. 二分

![在这里插入图片描述][baac8a71492b4f3aa0b409ca76ae6436.png_pic_center]

##### 第一讲 基础算法 #####

> 包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。

###### 2. 二分 ######

*  整数二分【两个模板】
    
     *  有单调性一定可以二分，可以二分的题目不一定有单调性
     *  本质：边界，即整个会被题目需求划成两半，一半满足，一半不满足
 *  浮点数
    
     *  本质也是边界
     *  边界很小的时候， 1 0 − 6 10^\{-6\} 10−6 多少多少这种，就可以认为答案已经出来了
     *  【比如求平方根这种题，二分做】
        
            #incldue <iostream>
            
            using namespace std;
            
            int main()
            {
                
                double x;
                cin >> 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\n", l);
                
                return 0;
            }
        
        ![在这里插入图片描述][0e220fd0be174ef09921d001e91850d7.png_pic_center]
        
        默认保留6 位小数，我们只需要保证比 精度多两位左右就可以了
        
        浮点数二分就没有边界问题，不会涉及到`+1`、`-1`，除了这种`while` 判断，也可以直接循环100次
        
        ![在这里插入图片描述][1e4ec400be1c403f88afb6b93bfc9d2f.png_pic_center]
        
        > 这里后面习题的时候y 总更正了左右边界，
        > 
        > ![在这里插入图片描述][812cc5db43974c4b8452d9008439883c.png_pic_center]
        > 
        > 当前的做法， 就是错误的
        > 
        > 改一下
        > 
        > ![在这里插入图片描述][57101b8404404858bee1f5230ceed26f.png_pic_center]
        > 
        > `x`不能小于1，所以取个较大值

> 两个模板

// 总归是看mid 属于左边还是右边
    // 区间[l, r]被划分成[l, mid] 和 [mid + 1, r] 时使用【mid属于左】
    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] 时使用【mid属于右】
    int bsearch_2(int l, int r)
    {
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid; // check()检查mid是否满足性质
            else r = mid - 1;
        }
        
        return l;
    }

`AcWing 789. 数的范围`

#include <iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    
    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;
    }

> 这道题就用到了两种模板，先把`mid` 写完，再想算`mid` 的时候要不要`+1`

习题，`AcWing 790. 数的三次方根`

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        double x;
        cin >> x;
        
        double l = -10000, r = 10000;
        
        while(r - l > 1e-8)
        {
            
            double mid = (l + r) / 2;
            
            if(mid * mid * mid >= x) r = mid; 
            else l = mid;
        }
        
        printf("%lf\n", l);
        
        return 0;
    }

> 浮点数二分

[baac8a71492b4f3aa0b409ca76ae6436.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a57c36fb8eca4d898dc82f92f448e6dc.png
[0e220fd0be174ef09921d001e91850d7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/23db0be6cb0546c09017b5db2d5a557a.png
[1e4ec400be1c403f88afb6b93bfc9d2f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9c4fd087894245138d30b31a3d36c29e.png
[812cc5db43974c4b8452d9008439883c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/13dc13f0ff6640ae8572ba63c597259c.png
[57101b8404404858bee1f5230ceed26f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/0303bdc67aac49db8eea7d4d50ef3cb9.png