🎯 二分算法
查字典时你不会从第一页开始翻，而是先翻到中间，看看要找的字在前半本还是后半本，然后一次次对半缩小范围。二分算法就是这个「每次砍一半」的聪明找法——从一亿个数里找一个数，最多只要猜 27 次！这一页学会二分查找，再学会把「猜答案」也做成二分。
考纲知识点：二分查找算法
二分答案算法（也称二分枚举法）
二分答案算法（也称二分枚举法）
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级
- (6)掌握二分查找和二分答案算法（也称二分枚举法）的基本原理，能够在有序数组中快速定位目标值。
📚
先学一学
花 5 分钟读完下面 5 课，再去闯关就不慌啦
1
🎮 猜数字游戏：每次都说「大了还是小了」
我心里想了一个 1~16 的数。聪明的猜法不是 1、2、3 挨个试，而是先猜中间数 8：如果小了，目标就在 9~16；再猜中间 12；再砍一半……每猜一次范围缩小一半，16 → 8 → 4 → 2 → 1，最多 4 次必中。范围扩大到 1~1024，也只要 10 次（因为 1024 = 2¹⁰）。
🧪 一次砍半的威力
· 挨个找（顺序查找）：1~1024 最多猜 1024 次。
· 二分猜：每刀砍半，最多约 10 次。
· 100 万个数：顺序找最多 100 万次，二分只要约 20 次！
· 二分猜：每刀砍半，最多约 10 次。
· 100 万个数：顺序找最多 100 万次，二分只要约 20 次！
💡 口诀：二分像折纸，对折再对折；次数 = 能砍几刀，也就是 log₂n。
📏 前提：数据必须「有顺序」
能判断「大了还是小了」，前提是数据已经排好序（像字典按拼音、电话簿按姓氏）。乱糟糟的一堆数没法说「目标在前半还是后半」，只能老老实实挨个找。
💡 口诀：要二分，先排队（排序）；没排序，只能一个个找。
2
🔎 二分查找：看中间，缩一半
在排好序的数组里找目标 target：① 看中间位置 mid 的数；② 若正好等于 target，找到了！③ 若 target 比它小，说明 target 只可能在左半边，把右边界移到 mid 左边；④ 若 target 比它大，就去右半边；⑤ 重复直到找到，或范围空掉（没找到）。
🧪 例子：在 [3, 7, 12, 18, 25, 30] 里找 12
整个范围下标 0~5，中间下标 (0+5)/2=2，a[2]=12，正好等于 target，一次就找到了！
如果找 7：a[2]=12 大于 7 → 去左半边 [3, 7]；中间下标 0~1 → (0+1)/2=0，a[0]=3 小于 7 → 去右半边 [7]；a[1]=7 找到。
如果找 7：a[2]=12 大于 7 → 去左半边 [3, 7]；中间下标 0~1 → (0+1)/2=0，a[0]=3 小于 7 → 去右半边 [7]；a[1]=7 找到。
💡 口诀：看中间，大了去左边，小了去右边；范围每次砍半。
💻 读代码：二分查找骨架
看得懂就好，不用背：
int l = 0, r = n - 1;
while (l <= r){
int mid = (l + r) / 2;
if (a[mid] == target) { cout << mid; return; }
else if (a[mid] > target) r = mid - 1;
else l = mid + 1;
}
cout << "没找到";
while (l <= r){
int mid = (l + r) / 2;
if (a[mid] == target) { cout << mid; return; }
else if (a[mid] > target) r = mid - 1;
else l = mid + 1;
}
cout << "没找到";
l、r 是左右边界；每次根据比较把边界挪到 mid 的左边或右边。
💡 口诀：左右夹击取中间，等于就停，大了挪右、小了挪左，空范围 = 没找到。
3
⚠️ 细节决定成败：边界别踩空
🎯 容易错的三处
· 循环条件 l <= r 还是 l < r：想清楚空范围什么时候出现。
· 挪边界要 mid - 1 / mid + 1，不是 mid——否则可能死循环。
· 求中间别用 (l+r)/2 溢出，可用 l + (r-l)/2。
· 挪边界要 mid - 1 / mid + 1，不是 mid——否则可能死循环。
· 求中间别用 (l+r)/2 溢出，可用 l + (r-l)/2。
💡 口诀：挪边界要越过 mid 再走一步；l+r 太大，改用 l 加半段距离。
4
🤔 二分答案：不找数，改「猜答案行不行」
有些题不是「找某个数」，而是「求一个最合适的答案」，比如把几根绳子切成指定数量的等长段，每段最长能多长？这种题可以二分猜答案：猜一个长度 mid，检查「按这个长度能切出目标段数吗？」——能，就说明 mid 可能还短，往更长的方向试；不能，就往短的方向试。反复砍半，最后锁定最合适的长度。这就是二分答案（二分枚举法）。
🧪 二分答案三步
① 定好答案的范围（比如绳长 0~最长那根）；② 写一个「检查函数」，回答某个长度可不可行；③ 对范围做二分：可行就往一个方向试，不可行就往另一个方向，直到范围缩到答案。
💡 口诀：二分答案 = 猜答案 + 问「行不行」；可行/不可行各占一边，砍半逼近最优解。
5
🆚 谁用二分 & 行业实际
🆚 顺序查找 vs 二分查找
· 顺序查找：不用排序，从第一个挨个找；100 万个数最坏找 100 万次。
· 二分查找：要求有序；100 万个数约 20 次。数据越多，二分优势越明显。
· 二分答案：答案本身不好直接算，但「猜一个值判断可不可行」很好写时，就用它。
· 二分查找：要求有序；100 万个数约 20 次。数据越多，二分优势越明显。
· 二分答案：答案本身不好直接算，但「猜一个值判断可不可行」很好写时，就用它。
💡 口诀：有序找数用二分，无序只能挨个问；不好直接算答案，二分答案来帮忙。
🌟 行业实际：二分无处不在
查字典、查电话号码、游戏里二分查 bug（把出问题的代码范围一次次砍半）、二分查找帮你定位一条记录……搜索引擎和数据库里到处都有二分的身影。它的复杂度只有 O(log n)，正是复杂度那页的「躺平省电模式」。
🎯
闯关小锦囊 · 考点提醒
- 二分查找：在有序数组里找目标，每次看中间、范围砍半，复杂度 O(log n)。
- 边界细节：循环条件、挪边界用 mid ± 1、中间下标用 l + (r-l)/2。
- 二分答案（二分枚举法）：猜一个答案并判断「可不可行」，按可行/不可行砍半逼近最优。
- 顺序查找不用排序但慢；二分要排序但飞快；无序数据不能二分。
- 二分要靠「跳到中间」，所以适合数组，不适合链表（链表走到中间就要花 O(n)）；找不到时会一直砍到范围为空才停下。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。