二分总结

步骤

1. 确定一个区间，使得目标一定在区间中。

2. 找到一个性质，满足：

   （1）性质具有二段性

   （2）答案是二段性的分界点

两类二分方法

第一类：ans（答案）是左侧区间的右端点

将[L,R]分为 [ L , M - 1 ] 和 [ M , R ] ，

如果mid落在左侧，说明ans仍在右侧区间 [ M , R ]

else 说明ans仍然在左侧区间 [ L , M - 1 ]

	while(l<r)
    {
        int m=(l+r+1)/2;
        if(m在左侧区间)
            l=m;
        else r=m-1;
    }  //结束时的情况是l=r

第二类：ans（答案）是右侧区间的左端点

将 [ L , R ] 分为 [ L , M ] 和 [ M + 1 , R ]

如果mid落在右侧，说明ans仍在左侧区间 [ L , M ]

else 说明ans仍然在右侧区间 [ M + 1 , R ]

	while(l<r)
    {
        int m=(l+r)/2;
        if(m在左侧区间)
            l=m+1;
        else r=m;
    }  //结束时的情况是l=r