📟作者主页：慢热的陕西人
🌴专栏链接：C++算法
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
主要讲解二分算法，分别讲解了整数二分和浮点二分
Ⅱ. 二分
思路：
二分的本质并不是单调性，二分的本质是存在一个边界使得点右边的区间满足条件，左边的区间不满足条件。
整数二分：
①
mid = (l + r + 1) >> 1加一的原因：当
l == r - 1的时候这时候mid == l,那么当我们check成功的时候就将l = mid相当于区间没有变死循环了；
if(check(mid)) l = mid; else r = mid - 1;
②
mid = (l + r) >> 1
if(check(mid)) r = mid; else l = mid + 1;
模板：
//区间为[l, r]被划分为[l, mid]和[mid + 1, r]时使用 //即符合条件的在mid左边，包括mid int bsearch(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右边包括mid int bsearch(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 mySqrt(int x) { double l = 0, r = x; while(r - l > 1e-11) { double mid = l + (r - l) / 2; if(mid * mid <= x) l = mid; else r = mid; } return r; }
到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话，可以点赞，收藏，顺便关注一下！
如果文章内容有错误，欢迎在评论区指正
