Dorado's host
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
友链
留言
关于我
登录
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
首页
›
学知识
›
二分算法
二分算法
2022-02-09 00:33
1122
0
## 思想 注意:**二分的本质不是单调性**。单调性可以理解为函数单调性,如一个数组是升序排列或降序排列,此时可以用二分来查找某一个数的位置。 有单调性一定可以二分,**但没有单调性,也有可能能够二分。** 二分的本质是边界。假设给定一个区间,如果能够根据某个条件,将区间划分为左右两部分,使得左半边满足这个条件,右半边不满足这个条件(或者反之)。此时就可以用二分来查找左右两部分的边界点。 理解起来有点复杂,那么我们还是拿一个例子来解释,对于一个数组`x = [1, 2, 4, -3, -5]`, 元素`x = 2`如果满足二元一次方程` x*x - 2*x + 1 `左边的函数值都比`x = 2`小,右边的函数值都比`x = 2`大的性质,则我们可以通过二分来找到他。 ## 整数二分 ### 思想 对于整数二分,我们先看这个图 ![截屏2022-02-08 下午11.29.35.png](https://dorado.host/usr/uploads/2022/02/2815424237.png) 现在我们看如何找到左边绿色的边界 ``` mid = (l + r + 1) / 2; // 为什么 +1 后面讲 if (check(mid)) { // check() 为满足绿色区间要求 // 此时答案肯定在(mid, r)中 l = mid; } else { r = mid - 1; } ``` 我们再来看如何找到右边红色的区间的边界 ``` mid = (l + r) / 2; if (check(mid)) { // check() 为满足红色区间要求 // 此时答案肯定在(l,mid)之间 r = mid; } else { l = mid + 1; } ``` ### **为什么l = mid需要 +1 ?** 思考当`l = r - 1 `时,此时`mid = (r + r - 1) / 2 = int (r - 1/2) = l`, 此时check命中的话区间仍为为`(l, r)`陷入死循环。 ### 板子 ``` // 区间划分为[l, mid],[mid + 1, r] int l = 0, r = n - 1; while(l < r) { int mid = (l + r) / 2; if(check(nums[mid])) r = mid; else l = mid + 1; } // 区间划分为[l, mid - 1],[mid, r] int l = 0, r = n - 1; while(l < r) { int mid = (l + r + 1) / 2; if(check(nums[mid)) l = mid; else r = mid - 1; } ``` ### 例题 ``` https://www.acwing.com/problem/content/791/ ``` ## 实数二分 ### 思想 实数二分很简单,可以想象成不需要处理边界的整数二分,这边我们用一道例题来看看。 ``` // 求x的算数平方更 #include
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", r); return 0; } ``` 原因是啥,因为整数是离散的,实数是连续的,l可以无限逼近r
相关文章
评论
(暂无评论)
取消回复
发表评论
dorado
一个平平无奇的打工人
17
文章
1
评论
12
栏目
热门文章
寻找两个正序数组的中位数
0 评论
ubutnu下的git常用命令
0 评论
IDEA快捷键一览(转)
0 评论
每日一报自动点击脚本
0 评论
端口查询
0 评论
更多