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

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

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

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

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

设一段区间[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;
      else	l=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;
    else	r=mid-1;
   }
   return 1;
}

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