first badversion用左闭右开区间有没有简洁的写法？

习惯了左闭右开区间模板，怎么用在这道题目上比起左闭右闭的写法要复杂？（终止条件后需要检查两个可能的位置）难道左闭右闭的写法有先天的优势？（终止条件后只需要检查一个可能的位置）能不能用左闭右开的写法并且终止条件后只需要检查一个可能的位置?

// 左闭右闭

1.     public int firstBadVersion(int n) {
   
2.         int l=1,r=n;
   
3.         while(l<r){ // 终止条件后只需要检查一个可能的位置： l
   
4.             int mid=l+(r-l)/2;
   
5.             if(isBadVersion(mid)) r=mid;
   
6.             else l=mid+1;
   
7.         }
   
8.         
   
9.         if(l>r) return -1;
   
10.         else return isBadVersion(l)?l:-1;
    
11.     }

复制代码

//左闭右开

1.   public int firstBadVersion(int n) {
   
2.         if(n<2) return 1;
   
3.         int b=1,e=n+1;
   
4.         while(b<e-2){ // 终止条件后需要检查两个可能的位置: b, b+1
   
5.             int mid=b+(e-b)/2;            
   
6.             if(isBadVersion(mid-1) e=mid // 而且为什么必须用mid-1的值？
   
7.             else b=mid;
   
8.         }
   
9. 
   
10.         return isBadVersion(b)? b: b+1; //终止条件后需要检查两个可能的位置
    
11. 
    
12.     }
    
13.         
    
14.     }

复制代码

补充内容 (2020-6-6 06:40):

loop invariant: 解存在于区间窗口中

2楼的写法是对的，我一直就这么写。我最近线段树也改成了左闭右开。

整个C++ STL的思想都是左闭右开，可以看看STL的源码。binary search看lower_bound()和upper_bound()的实现。https://en.cppreference.com/w/cpp/algorithm/lower_bound

gavinwWELL 发表于 2020-6-7 08:23
现学现用套用了几道题，这个技巧还挺好用的，请问有没有介绍类似技巧的书籍？谢谢

一些竞赛书里应该会有

gavinwWELL 发表于 2020-6-5 14:37
用这个loop invariant倒是解释得通了。

很巧妙，不过直观程度上能想出来也是不容易，厉害

我一般把binary search问题抽象成这样：已知存在一个函数f，在区间[begin, mid)函数值为True，在[mid, end)函数值为False，然后用bs求解mid。比如在First Bad Version这里，f就是isBadVersion。我的经验是，在别的binary search题目里，也可以这样formulate问题，求解也会比较轻松。

左闭右开：

1. class Solution {
   
2. public:
   
3.     int firstBadVersion(int n) {
   
4.         long long begin = 1;
   
5.         long long end = (long long)n + 1;
   
6.         while (begin < end) {
   
7.             long long mid = begin + (end - begin)/2;
   
8.             if (isBadVersion(mid)) {
   
9.                 end = mid;
   
10.             } else {
    
11.                 begin = mid + 1;
    
12.             }
    
13.         }
    
14.         return begin;
    
15.     }
    
16. };

复制代码

整个算法过程中不变的性质：(-inf, begin) 区间都是good version， [end, +inf) 区间都是bad version， [begin, end)未知。跳出loop后，begin和end重合，由前述性质可知，begin是第一个bad version。

hoooga 发表于 2020-6-6 06:27

运行通过， it just works, 但是无法理解：

1. if (isBadVersion(mid)) {
   
2.                 end = mid;
   
3.             }

复制代码

请解释一下，如果mid是bad version, , 那么mid也可能是解，但是把end设成mid岂不是把它排除在外了吗？
要知道左闭右开 [begin, end) 里面的end是不包括在区间里面的

我原回复后面增加了解释

hoooga 发表于 2020-6-6 06:27
左闭右开：

[mw_shl_code=bash,true]class Solution {

用这个loop invariant倒是解释得通了。

很巧妙，不过直观程度上能想出来也是不容易，厉害

loop invariant: 解存在于区间窗口中

gavinwWELL 发表于 2020-6-6 06:33
运行通过， it just works, 但是无法理解：
[mw_shl_code=java,true]if (isBadVersion(mid)) {
      ...

是的，所以写成 end = mid + 1 应该也行
edit：
哦不不行，会死循环……binary search真烧脑
这边如果 mid 是解，loop exit 的时候 low 就会是 mid，return low return 的就是解

hoooga 发表于 2020-6-6 06:27
左闭右开：

[mw_shl_code=bash,true]class Solution {

现学现用套用了几道题，这个技巧还挺好用的，请问有没有介绍类似技巧的书籍？谢谢