再谈Binary Search 模板while (left < right)的理解

我一般都是区间缩到足够小（比如小于8）就变成线性搜索，所以left=right的情况根本没有

先搞个模板，再理解模板。
不如先对过程建模，再理解这个过程，这样不需要记忆任何模板都能解决任何问题。

condition为true最左的点

1. while (left < right)
   
2. {  int mid = (left + right)/2;  //图省事，怕溢出自己改写一下好了
   
3.   if ( checkOK(mid)) { right = mid;} else { left = mid + 1;} } return left;

复制代码

condition为true最右的点 （division truncation防止死循环）

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

复制代码

值域是0到n-1的话，左右边界直接用0和n-1完了，貌似没那么麻烦。

比起左右端点这种几何意义上的理解，可以尝试从true/false来进行二分，左闭右开
while loop就可以变成
while(abs(t - f) > 1)
这样一套模板就可以ovo

knkm 发表于 2024-5-3 02:06
先搞个模板，再理解模板。
不如先对过程建模，再理解这个过程，这样不需要记忆任何模板都能解决任何问题。

说得非常好啊，那请问你是怎么对过程建模的呢？能否和大家分享一下？多谢

OnjoujiToki 发表于 2024-5-3 08:19
比起左右端点这种几何意义上的理解，可以尝试从true/false来进行二分，左闭右开
while loop就可以变成
wh ...

不好意思，没看懂啥意思

Falldawn 发表于 2024-5-3 23:30
说得非常好啊，那请问你是怎么对过程建模的呢？能否和大家分享一下？多谢

b站搜一下 "二分查找为什么总是写错？"这里就是一个建模的例子。

补充内容 (2024-05-03 23:34 +08:00):

包括quickselect这些，都可以对边界建模，这样就都不需要考虑边界问题了。因为在解答之前，边界问题已经被模型涵盖了

补充内容 (2024-05-04 01:32 +08:00):

有用这一层也可以加米

SoWhat0309 发表于 2024-5-3 08:07
condition为true最左的点condition为true最右的点 （division truncation防止死循环）值域是0到n-1的话，左 ...

左右边界为0和n-1显然不对，答案对了是因为没有提供完整的测试案例，不信你可以试试https://leetcode.com/problems/wa ... -sum-binary-search/

看看最高票答案种rwang778的回复，他的代码过不了一个测试案例，我也回复他了

knkm 发表于 2024-5-3 08:32
b站搜一下 "二分查找为什么总是写错？"这里就是一个建模的例子。

多谢多谢！虽然我上面讲的就是怎么能写对，也就是不会写错

之前都是在背模版，经常写错，后面看labuladong的二分模版讲解，理解了不少，会觉得他那样左闭右闭加上用<=确实更不容易出bug。最近正好在复习binarysearch，先收藏贴，后面好好看看楼主的分享