抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

二分模板

发布于：2023年4月16日

二分模板主要有两种：

模板1:
1
2
3
4
5
6
while (l < r)
    {
        int mid = l + r >> 1;	//(l+r)/2
        if (check(mid))  r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
模板2：
1
2
3
4
5
6
7
while (l < r)
   {
       int mid = l + r + 1 >> 1;	//(l+r+1)/2
       if (check(mid))  l = mid;
       else r = mid - 1;
   }

模板3：（浮点二分）
1
2
3
4
5
6
while(r-l>1e-5) //需要一个精度保证
{
	double mid = (l+r)/2;
	if(check(mid)) l=mid; //或r=mid;
	else r=mid; //或l=mid;
}

更新于：2023年4月16日

二分查找

评论