GESP5级C++考试语法知识（十七、二分算法提高篇（二））
《二分查找（二）——生死边界大冒险》
——l < r 和 l <= r 到底谁才是真正的勇者？
第一章：边界迷宫里的哭泣声
1、在算法大陆里，
很多小勇者已经学会了二分查找。
他们都知道二分模板是：
while(l < r) { int mid = (l + r) / 2; }2、可是考试时：
（1）有的同学：
💀 死循环
（2）有的同学：
💀 WA（答案错误）
（3）有的人：
💀 边界错一格
（4）还有人：
“我也不知道为什么，改着改着居然AC了……”
（5）于是，
二分王国里流传着一句话：
🌟“二分最可怕的不是不会写，
而是你以为自己会写。”
（6）今天，
汉克老师决定带同学们们进入：
《边界迷宫》
彻底弄懂：
while(l < r)和
while(l <= r)到底什么时候该用！
第二章：边界守卫出现了！
1、边界迷宫。
门口站着两个守卫：
2、左边这个叫：
🌟小于号守卫（l < r）
3、右边这个叫：
🌟小于等于守卫（l <= r）
4、两个守卫天天吵架：
“该用我！” “不对！该用我！”5、很多同学：
💫 当场懵掉。
6、汉克老师说：
“其实，他们都没错。”
“真正的问题是——”
🌟你维护的区间是什么？
第三章：什么叫“区间”？
1、汉克老师给大家展示了一个数组：
0 1 2 3 4这些是数组下标。
2、然后他说：
🌟二分查找，本质是在维护一个搜索区间！
也就是：
答案可能在哪儿？3、而区间，
有两大门派！
4、⚔️第一门派：[l , r)
（1）读作：
🌟左闭右开
（2）意思是：
l 能取到 r 取不到（3）例如：
[0,5)其实表示：
0 1 2 3 4不包含5！
5、🌟为什么很多人喜欢它？
因为：
r = n特别方便！
数组最后一个位置：
n-1而：
r=n刚好是：
🌟边界外一格！
第四章：左闭右开世界
1、汉克老师写下：
l = 0; r = n;代表：
区间是 [l,r)2、这时：
🌟什么时候区间还有东西？
（1）只要：
l < r（2）例如：
[2,5)（3）里面有：
2 3 4还有元素！
（4）那如果：
l == r（5）例如：
[5,5)里面有什么？
（6）🌟什么都没有！
区间空了！
（7）所以：
🌟循环条件必须是：
while(l < r)第五章：左闭右开的更新规则
1、在这个世界里，
最经典写法：
if(条件成立) r = mid; else l = mid + 1;2、具体分析为什么？
因为：
3、🌟情况1：mid可能是答案
（1）例如：
找第一个 >=x（2）如果：
a[mid] >= x（3）说明：
mid可能就是答案！（4）所以：
r = mid;保留mid！
4、🌟情况2：mid一定不是答案
（1）例如：
a[mid] < x（2）说明：
mid太小了！它一定不是答案。
（3）所以：
l = mid + 1;把mid扔掉！
第六章：另一大门派 [l,r]
1、接下来，
汉克老师带大家来到第二个门派。
🌟左闭右闭区间 [l,r]
2、意思：
l能取到 r也能取到例如：
[0,4]表示：
0 1 2 3 4全部都能取！
3、于是初始化：
l=0; r=n-1;因为：
n-1才是最后一个合法位置第七章：为什么这里是 l <= r？
1、因为：
只要：
l <= r区间还有元素！
2、例如：
[3,3]里面有什么？
3、🌟还有一个元素！
就是：
34、所以：
while(l <= r)必须让：
l==r这最后一个元素也参与检查！
5、只有：
l > r区间才真正空了。
第八章：为什么这里必须 r=mid-1？
这是容易错的地方！
1、汉克老师举例：
l=2 r=3计算：
mid=22、如果你写：
r=mid;会怎样？
3、新区间：
[2,2]还能继续。
4、但如果再下一次：
mid还是2就可能卡住。
5、更重要的是：
在“精确查找”里：
a[mid] != x说明：
🌟mid已经确定不是答案！
6、既然不是答案：
必须彻底扔掉！所以：
r = mid - 1;或者：
l = mid + 1;第九章：死循环怪兽再度出现！
有同学突然发现：
💀“死循环怪兽来了！”💀
1、来看：
l=2 r=3 mid=2如果：
l=mid;会发生什么？
2、下一轮：
l还是2 r还是3 mid还是2区间根本没缩小！
3、于是：
💀无限循环！
4、🌟死循环真正原因
不是：
while写错而是：
🌟区间没有缩小！
第十章：mid 的两种魔法
汉克老师再次画出两个点。
1、🌟左中点
mid=(l+r)/2特点：
偏左例如：
2 和 3mid：
22、🌟右中点
mid=(l+r+1)/2特点：
偏右例如：
2 和 3mid：
33、🌟最重要规律！
谁接mid，mid就不能站谁那边！
4、如果：
r=mid（1）说明：
要保留mid（2）那么：
mid必须 < r（3）所以：
🌟用左中点！
mid=(l+r)/25、如果：
l=mid（1）说明：
要保留mid（2）那么：
mid必须 > l（3）所以：
🌟用右中点！
mid=(l+r+1)/2第十一章：如何永远不再混乱？
汉克老师给大家：
🌟二分终极流程！
🌟第一步：先定区间！
到底是：
[l,r)还是：
[l,r]千万别混着写！
🌟第二步：根据区间决定while
1、如果：
l=0,r=n;那么：
while(l<r)2、如果：
l=0,r=n-1;那么：
while(l<=r)🌟第三步：确认mid是否保留
1、如果：
mid可能是答案2、保留：
r=mid或者：
l=mid3、如果：
mid一定不是答案4、丢掉：
r=mid-1或者：
l=mid+1🌟第四步：检查区间是否缩小！
这是最后保险！
每更新一次：
问自己：
新区间变小了吗？如果没有：
💀死循环警告！
第十二章：真正的二分高手
写二分时脑子里不是：
“我背哪个模板？”而是：
🌟我维护的是什么区间？
🌟mid是不是答案？
🌟区间有没有缩小？
只要这三句话清楚：
二分就不会错！
第十三章：课后训练
⚔️训练1
如果：
l=0 r=n应该写：
while( ? )为什么？
⚔️训练2
为什么下面可能死循环？
while(l<r) { int mid=(l+r)/2; l=mid; }⚔️训练3
什么时候应该写：
r=mid什么时候应该写：
r=mid-1⚔️训练4
请判断：
[3,3)里面有没有元素？
⚔️训练5
请判断：
[3,3]里面有没有元素？
第十四章：最终口诀宝典
🌟口诀1
先定区间！
🌟口诀2
[l,r)
对应：
while(l<r)🌟口诀3
[l,r]
对应：
while(l<=r)🌟口诀4
mid可能是答案：
保留mid！
🌟口诀5
mid不是答案：
扔掉mid！
🌟口诀6
每一步都要让区间缩小！
否则：
💀死循环！