二分查找,二分答案

include binary_search(a,a+n,value) 在递增序列中查找,找到返回true ,falselower_bound(a,a+n,value) 返回大于等于value的值lower_bound(a,a+n,value,greater()) 返回小于等于的值upper_bound(a,a+n,value) 返回大于value的值upper_bound(a,a+n,value,greater()) 返回小于value的值

1、最大化最小值
区间[l, r]划分成[l, mid - 1]和[mid, r]
整数:

while(l> 1; if(check())//当取这个mid时,能够满足条件,咋们找满足条件的最大值,则往右边搜索 l = mid;//答案在右边,往右边搜索 else r = mid - 1;}

浮点数:

while(r-l>0.00001)//最大化最小值{//保留4位小数 double mid = (r + l+0.00001) / 2;//可以写2.0000 if(check(mid)) l = mid; else r = mid;// - 0.00001保留精确度}cout << l << endl;

2、最小化最大值
将区间[l, r]划分成[l, mid]和[mid + 1, r]

while (l>1; if(check())//当取这个mid时,能够满足条件,咋们找满足条件的最小值,则往左边搜索 r = mid;//答案在左边,往左边搜索 else l = mid + 1;}

浮点数:

while(r-l>0.000001)//最小化最大值{ double mid = (r + l) / 2;//+ 2.0000 if(check(mid)) r = mid; else l = mid;//+ 0.000001}cout << l << endl;

浮点数可以通过循环100次来减小误差

for(int i=0;i<100;++i){ double mid = (r+l) >> 1; if(check(mid)) r=mid; else l=mid;}cout<< l << endl;

最短距离最大化问题：指的是每一个区间都有最小值,求每个区间最小值的最大值 保证任意区间距离要比最短距离mid大或相等（这样，mid才是最短距离）即：区间的距离>=mid mid逐渐增加直到不满足条件,则是每个区间最小值的最大值
最长距离最小化问题：指的是每一个区间都有最大值,求每个区间最大值的最小值 保证任意区间距离要比最大距离mid小或相等（这样，mid才是最大距离）即：区间的距离<=mid mid逐渐减少直到不满足条件,则是每个区间最大值的最小值
浮点数二分:
如果保留n位小数，while条件写 r - l > 1e-(n+2)
二分答案时,mid就是满足题意的值,可以依次对题目的条件进行判断,书写函数