关于二分法的边界问题

二分法的思想方法和问题辨识都挺简单的，但是每次针对具体问题写的时候经常出现TLE的情况。我后来根据
33. Search in Rotated Sorted Array
34. Search for a Range
81. Search in Rotated Sorted Array II
35. Search Insert Position
4. Median of Two Sorted Arrays
这几题总结出一个template，在以上题中都可以适用：

1. int l = 0, r = nums.size();
   
2.         while (l < r)
   
3.         {
   
4.             int mid = (l + r) / 2;
   
5.             if (nums[mid] == target) return mid;
   
6.             if (nums[mid] > target) r = mid;
   
7.             else l = mid + 1;
   
8.         }

复制代码

但是今天做到278. First Bad Version的时候发现solution里的code：

1. int firstBadVersion(int n)
   
2.     {
   
3.         int l = 1, r = n;
   
4.         while (l < r)
   
5.         {
   
6.             int mid = l + (r - l) / 2;
   
7.             if (isBadVersion(mid))
   
8.             {
   
9.                 r = mid;
   
10.             }
    
11.             else l = mid + 1;
    
12.         }
    
13.         return l;
    
14.     }

复制代码

右边界

因为这道题没有run test选项只能直接submit我做不了太多尝试，不过真的想不明白为什么 int l = 1, r = n; 这句不会导致TLE，根据之前总结的template，r=n+1才对。那个template是根据上面说的那5道题总结出来的，试错了很多次。。真心求问遇到bs的题大家都是怎么解的，尤其是对于边界问题的判定

首先，导致死循环的关键主要是L的变化方式，和hi的初始取值关系并不大。在你的模板里，把L=mid+1改成L=mid那就很可能会死循环。因为使用mid = (L+R)/2这种计算方式的话，当R-L=1时，mid是等于L的。而此时如果恰好执行了L=mid，那就意味着在这次iteration中，L的值没有变化，即搜索范围没有变，于是就死循环了。

至于R的取值方式不同，更多地是反映出实现者的思路不同：如果取成nums.size()，则可能意味着你认为目标可能出现在[L, R)中；hi取成nums.size()-1，意味着你认为目标一定会出现在[L, R]中。持前种思路的人，r = mid会更自然，而持后一种思路的人，则更可能会写r=mid-1 (当然他写成r = mid也是一样可以的)。

一个有助于你快速判断是否会死循环的方法，是考虑R-L=1的情况。在这种情况下target可能有小于，等于A[L], 小于，等于，大于A[R]共5种情况。快速验证一下这五种情况是否都能正常退出并返回正确值即可。

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

二分法是看起来非常简单，但是确很难写好的一个东东，变种花样也超多，哪位大佬能说说什么时候用 l <= r 什么时候用 l < r

第一个模板是找target
第二个是找满足条件的最小边界

还有，尽量避免用

(l + r)/2

这种写法，因为万一l + r overflow了那不就炸了

应该写

l + (r - l)/2

stellari 发表于 2017-10-26 09:30
首先，导致死循环的关键主要是L的变化方式，和hi的初始取值关系并不大。在你的模板里，把L=mid+1改成L=mid ...

啊刚看到，谢谢回复！的确是这样的，我总结出来的那个模板只是一种可能的写法。

1. r是包含还是不包含要考虑清楚，代码会长得不太一样，自己写和读别人的，都要先弄清这个。
这就像for (i=0;i<n;++i)和for (i=0;i<=n-1;++i)一样。
2. 数组长度还剩1是常见退出条件；不过数组长度2最好也单独讨论，容易出边界问题。

感觉
while(L < R)
然后，
如果是L 变(+1 或 -1) ,那么 m = (L + R) /2
如果是R 变(+1 或 -1),那么 m = (L + R + 1) /2

让m等于可以变的那个数，这样每次m就会得到不同的数
死循环的原因是因为m两次得到相同的值

我现在基本全用 while (lo+1 < hi)
这样保证不会TLE, 一定会在剩两种情况时退出