关于二分法的边界问题

我一般l-r<=1就手动判断了，l-r》=2的时候保证区间可以严格缩小。

我觉得九章的解法非常丑，二分法无非就是根据算出的m，判断这个位置的数据是否满足条件，然后再根据整个数据分布，判断潜在答案在哪边，去除另外一边。
只要保证每次都会丢掉至少1个元素，怎么样最终都会丢完，不可能会有死循环。我一直用while(l<=r)，很少写错导致死循环。

ronhao20171010 发表于 2017-10-25 13:51
还有，尽量避免用

(l + r)/2

其实还可以(l+r)>>>1

感觉已经快要被binary search给折腾死了～～～

好好分析

分享一个简单的边界处理

1. while (true) {
   
2.   if (r - l <= 4) {
   
3.     for (auto i = l; i <= r; ++i) {...}
   
4.     break;
   
5.   }
   
6.   auto m = (l+r)/2;
   
7.   // ...
   
8. }

复制代码

（滑稽

binary search最好用loop invariant去想，一个思维方式可以解所有相关题，有兴趣的同学可以search一下。

jason123 发表于 2018-2-4 00:59
我觉得九章的解法非常丑，二分法无非就是根据算出的m，判断这个位置的数据是否满足条件，然后再根据整个数 ...

while(l<=r)有种情况cover不了吧。某些情况下我们无法确定mid是否是我们需要的值，这样是不能保证每次都丢掉一个元素的。这种情况下我感觉还是得提前一步终止while循环，然后做一下后期处理，我这么理解对么

渣渣程序员 发表于 2018-4-18 16:30
while(l

我不是很清楚你说的是什么意思，但是我感觉你指的特请情况是“判断条件不是绝对相等”的例子。不是绝对相等，我指的是>= 或者 <=。
比如找一个区间内第一个不小于k的数(smalest number >= k)。
如论你的l 和 r 如何取，你通过现有的l 和 r的区间算出来一个m = l + (r - l)/2 ；这个m应该是这个区间里有效的一个数。
因为你要寻找的目标条件变化了，所以你判断m的条件也要变化。（核心）
if(m >=k) ，那么说明m是一个潜在的答案，你可以记录下这个答案，然后再丢掉，剩下的区间就在[l, m-1]
if(m < k)  ,   那么m就是一个废值，直接丢掉，剩下的区间就在[m+1, r]

这个记住潜在答案的实现方法有不同， 我是用一个ans的额外variable来记录的。
上述作法又有一点贪心的思想，就是只要剩下的区间是有效的，那么我就会在剩下的区间寻找更优解，一旦找到，我就会替换这个ans的variable的值。因为区间每次必定会丢掉一个数，所以一定不会死循环。

jason123 发表于 2018-4-23 12:43
我不是很清楚你说的是什么意思，但是我感觉你指的特请情况是“判断条件不是绝对相等”的例子。不是绝对相 ...

多谢回复啊。
我说的就是这种情况，因为如果m是一个潜在答案的话我们是无法直接丢弃的，所以可能会导致死循环。你的做法我理解了，就是用一个额外的变量来临时记录这个潜在的答案，然后保证每次都丢弃一个数，肯定也是可以的。