二分边界

jtzhang · 2018-09-08 14:02:13 · 个人记录

二分时，一定要保证无论什么情况都要有l或者r有改变。

1. 错误的二分：

   r= (l+r)/2+1;

   l= (l+r)/2；

   它们都存在无法改变的情况。

2. 正确的二分：

   a)当l<r时

           r= (l+r)/2;     
           l= (l+r)/2+1;

   b)当l<=r时

   
           r= (l+r)/2-1;       
           l= (l+r)/2+1; ``` 
           此时必须记录下已经搜过的答案，因为这样必须舍弃一边
   
    **这种方法适用于想同时保存左右两个端点时。**
   
   我们可以考虑（l+r）/2+1 必然>l ，而 （l+r）/2 必然小于r。
   
       而mid究竟是为(l+r)/2还是(l+r)/2+1， 完全取决于你是否想保留mid所指向的值 和 所答案取向(合法值在mid左侧还是右侧) 决定。