1)确定区间(目标值一定在区间内)
2)找一个性质,满足:①性质具有二段性②答案是二段性的分界点
第一类:m为红色右端点
while(l<r)
{
mid=(l+r+1)/2; //+1处理边界问题
if(m属于红色区域,右端点)l=m;
else r = m-1;
}
第二类:m属于绿色左端点
if(m是绿色) //说明ans必然在m的左边
else ans 在[m+1,r]
while(l<r)
{
m = (l+r)/2;
if(m是绿色)r=m; //不需要加1
else l = m+1;
}
实数二分:
将区间[l,r]划分成[l,m] [m,r]
if(ans在区间[m,r]) l=mid;
else if (ans在区间[l,m]) r =mid;
while(r-l>1e6)
{
double M = (l+r)/2;
if()l=mid;
else ()r=mid;
}