讨论一下如何写 binary Search （比如lower/uppper bound)

我一般是 left + 1< right 然后再考虑循环结束后left right的位置的情况

牛牛牛ALLU 发表于 2020-8-13 19:17
我自己也是对binary search有很多疑问。有时候if statement的顺序也有影响。还有时候l = mid + 1 还是l = m ...

left 是该等于mid 还是 mid + 1, 个人觉得这个是要根据“mid的值会不会是最终结果”，如果确定不是的话就可以mid+1了，mid+1的意思就是放心大胆的把mid的值排除。

https://leetcode.com/discuss/gen ... olved-many-problems

EDC666 发表于 2020-8-14 06:23
left 是该等于mid 还是 mid + 1, 个人觉得这个是要根据“mid的值会不会是最终结果”，如果确定不是的话就 ...

我有提到这个situation，有时候你知道mid不会是最终结果，但是还是left=mid

其实你可以理解一下什么叫lower bound。lowerbound其实指的是满足某种条件的下界。
二分查找可以理解成找到一个边界，左边符合某个条件，右边符合另一个条件。
lower bound指的就是右边的最左端点。

1. while (left < right) {
   
2.     int mid = (left + right) / 2;
   
3.     if (arr[mid] < target) {
   
4.         left = mid + 1;
   
5.     } else {
   
6.         right = mid;
   
7.     }
   
8. }
   
9. return left;

复制代码

这段代码求的其实是arr[j] >= target的最小下标。也就是lower bound。
为什么left要等于mid加一呢，因为mid不满足这个条件，所以mid不会成为最终的分界点。
right确实是可以成为分界点的。

leetcode上面就有binary search的三种用法，以及他们适合的场景。你自己试着用一种去套其他的，有些是可以的，但是需要多几行代码，有些是不行的，就知道啥时候该用哪个了。

https://www.1point3acres.com/bbs/thread-660719-1-1.html

我一般都用同一个模板，左闭右开
while (l < r) {
    m = l + (r - l) / 2
    if (f(m)) {
        r = m
    } else {
        l = m + 1
    }
}
这样可以求出令 f(l) == true 的l 的最小值，如果l == r则不存在

在leetcode里这个方法几乎可以ac所有的二分题.p.s. 如果觉得有用的话求米

楼主看看这个
https://www.cnblogs.com/grandyang/p/6854825.html

感觉就是边界条件就是记下来，凭肌肉记忆。