如何说明“类二分搜索”结果的正确性？采用[left, right)区间

最正常的二分搜索，在一个数组中用左右都是闭区间[left, right]的方法二分搜索一个数字，只要mid指向的那个数字是你要的target，那肯定就找到，这个结果的正确性非常好理解。
刷题时还见到过一种左闭右开[left, right)的二分搜索非常流行，最后的结果是left指向的值，这个我就不太能理解了
比如LC658票数最高的答案：https://leetcode.com/problems/fi ... ts/discuss/106419/O(log-n)-Java-1-line-O(log(n)-%2B-k)-Ruby
为什么能保证最后跳出while循环时left/lo的值就是正确的？该如何理解这种二分搜索呢？


补充内容 (2019-1-4 07:16):
https://leetcode.com/problems/fi ... ts/discuss/106419/O(log-n)-Java-1-line-O(log(n)-%2B-k)-Ruby

补充内容 (2019-1-4 07:17):
如果上面链接挂了点这里

一般这种题目我都用额外一个变量 记录目前为止找到的 最大/最小的结果的 idx.  然后继续往更大/更小方向找.   while是  start ＜＝ end.  因为每种情况我都会 移动至少一个单位 所以不会有死循环

可以考虑一下

lz我常用的办法是极限法，你如果对跳出循环的条件不自信，可以想象最后只剩两个点，和三个点的情况，你就按照只剩star和end两点，或者start mid end三点来写你的循环逻辑，如果这两种情况ok那么其他任意数量的节点进入你的循环都没问题。假如我没理解错你可以参考一下first bad version那题。标准答案是返回start也就是left应该是属于你说的左闭右开

我用同样的方式写了比较简单的例子，给一个数组arr，给了一个目标值x

1. public int get(int[] arr, int x) {
   
2.     int lo = 0, hi = arr.length-1;
   
3.     while (lo < hi) {
   
4.         int mid = (lo + hi) / 2;
   
5.         if (arr[mid] >= x) // 需要满足的条件
   
6.             hi = mid;
   
7.         else
   
8.             lo = mid + 1;            
   
9.     }
   
10.     return arr[lo];
    
11. }

复制代码

这个代码实现的效果是，找到数组中大于等于x的最小下标，抽象的说就是满足条件的最小下标（条件就是if中的判断条件），对不同的题目if里面的条件肯定不一样
这是为什么呢？
lo，hi在这段代码里表示的是[lo, hi]闭区间，如果下标mid满足条件让hi=mid，这就说明满足条件的会保留在区间里，不满足的逐步被清出去。
1.当数组只有一个元素满足条件时，必然最后lo会和hi碰头，剩下的就是所求元素。
2.当有多个满足条件时，会出现[lo, hi]里面全都满足条件，这时候mid取(lo+hi)/2，因为此时mid也满足条件，会使得hi=mid，右边界逐渐逼近左边界，最后出现hi==lo+1时，求得mid=(lo+hi)/2=lo，使得hi=mid=lo，跳出循环。所以最后hi会指向最小下标
3.当没有元素满足条件，lo不断变大，直到和hi碰头，但是所指元素并不满足条件
这个写法最后lo是保证了和hi相等才会退出，另外为了最后lo指向的位置记得多加个判断来排除3的情况
现在回到LC658这个题目，首先我觉得这个题目能想到用二分做是这道题比较刁钻的地方，题目让我们求离x最近的k个数，当出现tie的时候取小下标。而正好上面已经解释过了这个写法能实现满足条件的最小下标，所以剩下就只用整明白解答里的if条件。我们可以用一个下标窗口[l, l+k)来在数组上滑动确定答案，并且保证l越小越好。
下面的“距离”是指差值的绝对值。
因为要确定最接近的K个，也就是说窗口内的数和x的“距离”要小于等于窗口外的数到x的“距离”，然后因为要保证l越小，则arr[l]肯定就是窗口内"距离"最大的数了，所以要拿arr[l]和窗口外的数比，用二分求边界l。二分里面mid就是要求的边界，用mid和窗口外的mid+k做比较，只要arr[mid]的"距离"小于等于arr[mid+k]的“距离”就是满足答案要求的窗口，所以条件部分我们可以写

1. while (l < r) {
   
2.             int mid = (l + r) / 2;
   
3.             if (x - arr[mid] <= arr[mid+k] - x) r = mid;
   
4.             else l = mid+1;
   
5.         }

复制代码

即高票答案的if (x - arr.get(mid) > arr.get(mid+k) - x) lo = mid + 1;

最后对于二分写法开始的时候自己见过蛮多的，之前也各种懵逼，最后还是找了一个自己理解的背了下来（就是高票写的这个当模版用了）。对于不同的写法没好坏之分，但是一定要确保知道下标最后指的位置是什么含义，要不然很容易写跪掉。。。另外和前几层的同学说的一样，可以用l=x, r=x+1来检查自己二分的写法会不会出现死循环之类的（这个是在另一个地方学到的，里面还有更深入的二分讨论，链接见此）