二分模板一共有两个,分别适用于不同情况。
算法思路:假设目标值在闭区间[l, r]中, 每次将区间长度缩小一半,当l = r时,我们就找到了目标值。
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。
找右边绿色部分的左边界
C++ 代码模板:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;//此时l和r相等吗?
}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。 mid在右边时需要+1 找左边红色区域的右边界
C++ 代码模板:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分:一种是用for循环循环100(好多)次;
另一种是while循环->while(r-l>1e-6)//大于的那个数根据题目的实际情况比保留的小数位数多两位时候最合适
#include <iostream>
using namespace std;
int main()
{
double x;
cin>>x;
double l = 0, r = x;
while(r - l > 1e-6)//精确度随题目条件而定 比题目规定的多两位即可
{
double mid = (l + r) / 2;
if(mid * mid >= x) r = mid;
else l = mid;//这里不需要再加一,比整数二分容易点
}
printf("%lf\n",l);
return 0;
}
作者:yxc
链接:https://www.acwing.com/file_system/file/content/whole/index/content/3073/
来源:AcWing
二分的过程中,如果你超时了,你就l + r + 1>> 1;如果没超时就l + r >> 1
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH