关于二分法中取中间值时向下和向上取整的有关问题（由大白LA3971想到的）

关于二分法中取中间值时向下和向上取整的问题（由大白LA3971想到的）

最近在做刘汝佳的大白，有一道题目LA_3971，也是UVA_12124，是用二分法做的。

题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=3276代码如下

while(L<R){        M=(L+R+1)/2;        if(ok(M))              R=M;        else              L=M+1;}

L R M

0  5 3

0 3 2

0 2 1

0  1 1

0 1 1

。。。

又陷入了死循环，但是我们可以发现如果这时用向下取整就是可行的了。

所以由上面就可以得出，

当我们使用二分法求某个合理区间最值的时候，我们要十分注意两个端点的极端值的情况。

当然还有一种更保险的方法

那就是不用上面的二分的方法

在二分的时候用另外一个变量来记录合理值，然后L=M+1  OR   R=M-1

所以这样的话是不回陷入到死循环里面去的

这就是我由这T想到了，好久不写博客了。还是要捡起来啊。