0.前言

通过几道题目 切割钢管、木材加工、切割绳子、均分蛋糕 四道题，尝试了二分法中最大化平均值问题。

然后，下面进行简单的对比和总结。

1.简单总结

while(l < r){
        int mid = (l + r) >> 1;// 二分查找
		int cnt = 0; 
        for(int i=0;i<n;i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){ 
            //那么这个mid是可行的，我们就可以扩大左边界值
            l = mid + 1;
        }else{
            r = mid;
            //否则的话，这个mid就是太高了，就可以把右边界缩小
        }
    }

写法2：

while(l <r-1){
        int mid = (l + r) >> 1;// 二分查找
		int cnt = 0; 
        for(int i=0;i<n;i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){ 
            //那么这个mid是可行的，我们就可以扩大左边界值
            l = mid;
        }else{
            r = mid;
            //否则的话，这个mid就是太高了，就可以把右边界缩小
        }
    }

写法2进行简单变换还可以写成：

while(l+1 <r){
        int mid = (l + r) >> 1;// 二分查找
		int cnt = 0; 
        for(int i=0;i<n;i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){ 
            //那么这个mid是可行的，我们就可以扩大左边界值
            l = mid;
        }else{
            r = mid;
            //否则的话，这个mid就是太高了，就可以把右边界缩小
        }
    }

如果出现小数，那么可以这么写：

while ((right-left)>1e-4) 
{
	mid=(left+right)/2;
	for (i = 0; i < n; i++)
		num += (int)(a[i] / x);
	if(sum>=k)
		left=mid;
	else
		right=mid;
}
//1e-4=0.0001
//等价于下面这样: 
while (left+1e-4<right) 
{
	mid=(left+right)/2;
	for (i = 0; i < n; i++)
		num += (int)(a[i] / x);
	if(sum>=k)
		left=mid;
	else
		right=mid;
}

注意: 这类题目的最大值一般通过循环求出，一般单体的最大值作为初始右端点，或者单体和的最大值作为右端点。

然后，有一类写法带等号

变形：（带等号的左右端点都要变）

while(l <= r){
        int mid = (l + r) >> 1;// 二分查找
		int cnt = 0; 
        for(int i=0;i<n;i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){ 
            //那么这个mid是可行的，我们就可以扩大左边界值
            l = mid + 1;
        }else{
            r = mid - 1;
            //否则的话，这个mid就是太高了，就可以把右边界缩小
        }
    }

2.题目扩展

可以有单一的线条类型，变成复杂的面积、体积等类型。比如均分蛋糕

3.说明

上述过程，我们大部分都是在取左端点，其实可以取右端点。比如下面这两个代码模板：

取左端点：

while (l < r) {
	int mid = (l + r) / 2;
	if (judge(mid))
		r = mid;//judge()函数判断是否在范围内，为布尔型
	else
		l  = mid + 1;//避免死循环
}
return l;

取右端点：

while (l < r) {
	int mid = (l + r + 1) / 2;//+1避免死循环
	if (judge(mid))  
		l = mid;
	else  
		r = mid - 1;
}
return 1;

4.本质

二分：自定义某一性质，让区间的左边元素均不满足，右边元素均满足。或者反过来。