二分（整数二分和浮点数二分）

二分法

二分法能解决的问题二分法的本质二分的条件二分的思想二分模板（整数二分）浮点数二分 二分法能解决的问题

用于一段区间求满足题意的单点问题，某个性质将区间分成满足性质和不满足性质的两半，二分法就可以寻找该性质的两个边界（即不满足性质的边界和满足性质的边界），但要注意边界问题十分重要

二分法的本质

二分的本质是用一个判定问题来代替查找，逐步缩小区间锁定答案，二分部的本质不是单调性。

二分的条件

一定要在有序的数列中查找。

二分的思想

设一段区间[l,r]，某性质将区间[l,r]分成两部分，前部分不满足该性质，后半部分满足该性质，前部分的分界点为点（1）区间为[l,(1)]，后部分的分界点为点（2）区间为[(2),r]。
1.找到区间[l,r]中间值mid
2.检查mid是否满足该性质，判定满足和不满足，根据mid所在区间去更新区间缩小范围。

拿到一个二分题目首先要要思考那个性质可以分好区间，判定mid后该如何缩小区间。

二分模板（整数二分）

二分模板根据划分的区间不同有两个

1.当区间[l,r]划分成[l,mid]和[mid+1,r]时，更新操作 r=mid(答案区间在【l,mid】) 或 l=mid+1(答案区间【mid+1,r】)计算mid时不需要加1.（一般求点（2））int bsearch_1(int l,int r){ while(l>1;//下取整 if(check(mid))r=mid; elsel=mid+1; } return l;}2.当区间[l,r]划分成[l,mid-1]和[mid,r]时，更新操作 r=mid-1(答案区间在【mid，r】)或 l=mid(答案区间在【l,mid-1】)计算mid时需要加1.(一般求点（1）)int bsearch_2(int l,int r){ while(l>1;//上取整 if(check(mid))l=mid; elser=mid-1; } return 1;}

浮点数二分

浮点数二分相比较于整数二分无边界问题，也可借助于整数二分的模板下面就举例解释一下：eg:求x的平方根#includeusing 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("%lfn",l);return 0;}