GESP5级C++考试语法知识（十七、二分算法提高篇（一））

⚔️《二分查找王国大冒险》⚔️——真正掌握二分不再靠“改一改试一试”第一章勇者小明与“百万藏宝箱”1、很久很久以前在“算法大陆”里有一个叫小明的小勇者。有一天国王交给他一个任务“这里有 1000000100万个宝箱只有一个箱子里藏着黄金钥匙你要尽快找到它”2、小明第一反应“那我一个一个找呀”于是第1个不是第2个不是第999999个还不是……小明直接累趴。3、这时候汉克老师出现了“同学们你们这样找太慢了。”“你们需要学习一种超级强大的魔法——”二分查找第二章什么叫“二分”1、汉克老师拿来一张按顺序写满数字的纸条1 2 3 4 5 6 7 8 9 10现在要找数字8。1普通方法1个个看2而二分法直接看中间3中间是谁5因为8 54所以左边全部不要了瞬间砍掉一半5只剩6 7 8 9 106再看中间8找到了2、这就是二分的威力1每次砍掉一半2时间复杂度O(log n)3100万个数只需要查大约20次第三章真正的本质是什么1、很多同学以为“二分就是不断找中间。”2、❌ 错二分真正的本质是寻找“分界线”3、比如数组1 2 2 2 3现在找第一个 2 的位置4、我们把每个位置变成“是否满足条件”。1条件a[i] 22于是得到1 2 2 2 3 ❌ ✅ ✅ ✅ ✅3你发现没有这里有一条神奇的边界❌ ❌ ❌ | ✅ ✅ ✅4而二分查找就是寻找这条边界第四章二分最重要的三句话汉克老师认真地说第一句你到底找什么你要找第一个满足最后一个满足还是随便一个不同目标模板不同第二句mid 是答案吗1如果mid可能是答案2那就保留mid3否则丢掉mid第三句区间有没有变小二分最怕死循环原因只有一个区间没缩小第五章死循环怪兽登场1、来看l 2 r 32、计算mid (23)/2 23、如果你写l mid;会发生什么4、下一轮l还是2 r还是3 mid还是2永远不变5、于是进入无限死循环第六章mid 的两种身份汉克老师在黑板上写下两个点1、左中点mid (lr)/2例如2 和 3mid2偏左。2、右中点mid (lr1)/2例如2 和 3mid3偏右。3、超级重要规律汉克老师讲到“谁接midmid就不能站谁那边”什么意思4、如果 mid 是左中点mid(lr)/2那么不能 lmid因为 mid 可能等于 l会卡住5、如果 mid 是右中点mid(lr1)/2那么不能 rmid因为 mid 可能等于 r6、一句口诀左中点别写 lmid右中点别写 rmid第七章五大二分神技⚔️第一招找第一个 ≥ x1、比如1 2 2 2 3找第一个 2答案位置12、思考如果a[mid] x说明mid可能是答案所以rmid保留它3、代码int find(vectorint a,int x) { int l0; int ra.size(); while(lr) { int midl(r-l)/2; if(a[mid]x) rmid; else lmid1; } return l; }⚔️第二招找第一个 x只需要改一个地方if(a[mid]x)⚔️第三招找最后一个 ≤ x这次满足条件继续往右找所以lmid1最后答案l-1⚔️第四招找最后一个 x和上面几乎一样。⚔️第五招精确查找这个大家最熟悉while(lr)因为左右边界都可能是答案代码int find(vectorint a,int x) { int l0; int ra.size()-1; while(lr) { int midl(r-l)/2; if(a[mid]x) return mid; else if(a[mid]x) lmid1; else rmid-1; } return -1; }第八章为什么有时候是 lr1、很多同学最迷糊while(lr)和while(lr)到底区别是什么情况1寻找边界1例如第一个 ≥x最后一个 ≤x2这种答案一定存在于某个区间3我们维护的是[l,r)左闭右开区间。4所以while(lr)5因为当 lr 时 区间已经空了搜索结束。情况2精确找数字1例如找有没有等于x2此时每个点都可能是答案3所以while(lr)必须让最后一个点也检查。第九章真正的二分高手怎么思考真正厉害的人脑子里想的不是套哪个模板而是第一步条件是什么例如a[i]x第二步哪些是❌哪些是✅例如❌ ❌ ❌ ✅ ✅ ✅第三步我要找哪条边界例如第一个✅第四步mid 要不要保留如果mid可能是答案就保留否则丢掉第十章终极口诀汉克老师最后送给大家的口诀二分查找四大口诀口诀1二分不是找数字而是找边界口诀2先想分界线❌❌❌✅✅✅再写代码口诀3mid包含与不包含mid可能是答案rmidmid不可能是答案lmid1口诀4区间必须缩小否则死循环第十一章课后挑战1、挑战1数组1 3 3 3 5 7请找第一个 3答案是多少2、挑战2请找最后一个 33、挑战3为什么下面会死循环while(lr) { int mid(lr)/2; lmid; }第十二章最终奥义真正掌握二分的人看到一道题时第一反应不是“我要背哪个模板”而是“这里有没有单调性”“我在找哪条边界”一旦学会这个思想你会发现二分答案二分最大值二分最小值二分函数全部都能打通因为所有二分本质都一样。