AcWing算法基础课学习笔记 第一讲 基础算法 2. 二分 叁歲伎倆 2024-03-16 11:53 58阅读 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
相关 AcWing算法基础课学习笔记 第一讲 基础算法 2. 二分 AcWing算法基础课学习笔记 文章目录 AcWing算法基础课学习笔记 第一讲 基础算法 叁歲伎倆/ 2024年03月16日 11:53/ 0 赞/ 59 阅读
相关 AcWing算法基础课学习笔记 第一讲 基础算法 1. 排序 AcWing算法基础课学习笔记 文章目录 AcWing算法基础课学习笔记 第一讲 基础算法 小咪咪/ 2024年03月16日 11:52/ 0 赞/ 53 阅读
相关 acwing算法基础课学习笔记(第一章:基础算法) 第一章:基础算法 前言 一、快速排序 1. 快速排序算法模板 2. 快速排序模板题(1):快速排序 3.快速排序算法模 小鱼儿/ 2023年09月28日 18:18/ 0 赞/ 32 阅读
相关 Acwing - 算法基础课 - 笔记(五) 文章目录 数据结构(二) Trie树 练习题:\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 162 阅读
还没有评论,来说两句吧...