专题 15 二分查找 · 复习强化

考点：查找问题与返回值（A1）。

（A1）考点：查找问题与返回值——查找函数找到目标返回其所在下标，失败约定返回 $-1$。

解析：本题考查查找问题与返回值。下标能定位元素在数组中的位置，是查找的自然答案；$-1$ 不是任何合法下标，用作失败标记不会与真实结果混淆。

排除法：A A 以为返回元素值的人没注意「值调用方本来就有」，位置才是新信息；D D 以为返回数组长度的人混淆了查找与计数；C C 以为返回首下标的人没想过目标可能不在开头。

考点：顺序查找适用场景（A2）。

（A2）考点：顺序查找适用场景——数据无序、查询次数少时，直接顺序扫描最合算。

解析：本题考查顺序查找适用场景。顺序查找零前提、零预处理：数据乱序、只查一两次，排序的预处理成本收不回来，逐个比较反而是最优解。

排除法：D D 选已排序多次查询的场景应该排序后二分；B B 选要求十几次比较的场景只有二分达标；C C 选有序结构的场景同样有更快的选择。

考点：顺序查找最坏次数（A3）。

（A3）考点：顺序查找最坏次数——$n$ 个元素最坏要比较 $n$ 次。

解析：本题考查顺序查找最坏次数。最坏情形是目标在最后一位或不存在：从下标 $0$ 一路比到 $n-1$，共 $n$ 次比较，复杂度 $O(n)$。

排除法：B B 答 $n/2$ 的人把平均情况错当成最坏情况；D D 答 $\log_2 n$ 的是二分的量级，顺序查找没有折半；A A 答 $1$ 的是最好情况。

考点：顺序查找平均次数（A4）。

（A4）考点：顺序查找平均次数——目标等概率在各位置时，平均比较约 $(n+1)/2$ 次。

解析：本题考查顺序查找平均次数。目标在第 $i$ 位（$1$ 起）要比较 $i$ 次，各位置等概率时平均为 $(1+2+\cdots+n)/n=(n+1)/2$，约是数组的一半。

排除法：D D 答 $n$ 的人把最坏当平均；A A 答 $\log_2 n$ 的是二分的量级；B B 答 $n^2/2$ 的人把「比较次数」与「所有对组合」混在了一起。

考点：链表只能顺序查找（A5）。

（A5）考点：链表只能顺序查找——链表不支持随机访问，只能沿指针逐个走。

解析：本题考查链表只能顺序查找。数组能一步跳到任意下标，链表想看第 $k$ 个元素必须从头走 $k$ 步，任何「跳着查」的策略都无从谈起。

排除法：B B 以为链表元素无序的人没抓住要害——就算排好序，定位不了中点照样无法折半；C C 以为内存不连续就不能存整数的把两件不相干的事扯在一起；D D 以为指针不能比较的没注意比较的是数据域。

考点：数组下标从零开始（A6）。

（A6）考点：数组下标从零开始——C++ 数组下标从 $0$ 到 $n-1$。

解析：本题考查数组下标从零开始。int a[8] 的合法下标是 $0$ 至 $7$，查找循环从 $0$ 起到 $7$ 止，数错边界就会漏元素或越界。

排除法：D D 答 $1$ 到 $8$ 的人沿用了日常计数习惯；B B 答 $0$ 到 $8$ 的人把 $8$ 也算进去造成越界；C C 答 $1$ 到 $7$ 的人两头都数错。

考点：哨兵法省边界判断（A7）。

（A7）考点：哨兵法省边界判断——末尾放待查值作哨兵，循环不必判断下标越界。

解析：本题考查哨兵法省边界判断。哨兵保证循环一定能遇到目标值停下，循环条件只剩「值是否相等」一项，每轮少一次越界检查。它不改变最坏比较次数的量级。

排除法：B B 以为哨兵让数组有序的人混淆了查找与排序；A A 以为把最坏变最好的人不了解哨兵只是省判断不省比较；D D 以为减少比较次数上限的人同样高估了它——上限仍是走到哨兵为止。

考点：顺序查找综合判断（A8）。

（A8）考点：顺序查找综合判断——顺序查找零前提、代码简单，但最坏比较与元素个数同阶。

解析：本题考查顺序查找综合判断。它对数据无任何要求，这是它最大的优点；代价是线性时间，数据量大时力不从心。

排除法：A A 以为要求数据有序的人把它和二分的前提弄混；C C 以为每次排除一半的人描述的是二分；D D 以为复杂度是对数级的人同样把两种算法的量级张冠李戴。

考点：二分的基本思想（B1）。

（B1）考点：二分的基本思想——与中间元素比较，每次把候选区间缩小一半。

解析：本题考查二分的基本思想。有序性保证比较结果能判断目标在左半还是右半，于是每轮安全地丢弃一半候选，$n$ 个元素最多 $\log_2 n$ 轮出结果。

排除法：B B 选逐个向后移动的人描述的是顺序查找；D D 选分四份同时查找的不是二分的形态；C C 选随机挑元素比较的没有任何「排除一半」的保证。

考点：二分的前提条件（B2）。

（B2）考点：二分的前提条件——数组有序且支持随机访问。

解析：本题考查二分的前提条件。有序保证方向判断成立，随机访问保证取中点是常数时间，两者缺一不可。元素可以重复、长度不必是 2 的幂、正负数都无妨。

排除法：D D 选元素互不相同的人加了不存在的前提，重复元素照样可二分；A A 选长度是 $2$ 的幂的人把「对数次收缩」误解成了对数据规模的形状要求；C C 选都是正数的人给有序性加了无谓限制。

考点：比较后的收缩方向（B3）。

（B3）考点：比较后的收缩方向——升序中 a[mid] < x 说明目标只可能在右半。

解析：本题考查比较后的收缩方向。升序数组里 a[mid] 及其左侧都不超过 a[mid]，而 a[mid] 已小于 x，整段左侧被一次性排除，下一步 l = mid + 1。

排除法：D D 选去左半的人把不等号方向想反，会背弃目标所在方向；B B 选从头重来的人丢掉了已经获得的信息；A A 选宣布不存在的人把「中点不是目标」误解成「全都不是」。

考点：二分比较次数量级（B4）。

（B4）考点：二分比较次数量级——二分查找时间复杂度 $O(\log_2 n)$。

解析：本题考查二分比较次数量级。每轮候选减半：$n$、$n/2$、$n/4$……直到剩 $1$ 个，轮数是 $\log_2 n$ 量级，百万元素也只要二十轮上下。

排除法：D D 答 $O(n)$ 的是顺序查找的量级；B B 答 $O(n\log_2 n)$ 的是排序的量级——若先排序再查一次，总代价确实由排序主导；C C 答 $O(1)$ 的人忘了查找至少要比较一次。

考点：二分与顺序速度对比（B5）。

（B5）考点：二分与顺序速度对比——百万元素二分约 20 次，顺序最坏 100 万次。

解析：本题考查二分与顺序速度对比。$2^{20}\approx 104$ 万，二分最多比较约 $20$ 次；顺序查找最坏要把每个元素都看一遍，即 $100$ 万次，两者相差五万倍。

排除法：D D 答 $20$ 次的人把二分的次数错记到顺序头上；C C 答 $1000$ 次的人量级估算失真；A A 认为在 $50$ 万与 $100$ 万之间无法确定的人不了解最坏情况的上界是确定的——最多 $100$ 万次就是定论。

考点：二分的本质是收缩（B6）。

（B6）考点：二分的本质是收缩——每轮维护一个可能包含目标的候选区间并减半。

解析：本题考查二分的本质是收缩。l、r 圈出候选范围，每轮用一次比较把范围砍半，区间空了（没找到）或命中为止。抓住这个不变量，各种变体都是同一骨架。

排除法：D D 选计数器的人把循环变量当主角；B B 选维护有序性的人没注意有序是前提不是被维护的东西；A A 选目标副本的人凭空想象了一个不存在的数据。

考点：链表不能高效二分（B7）。

（B7）考点：链表不能高效二分——定位链表中间节点本身就要线性时间。

解析：本题考查链表不能高效二分。二分省时间的关键是「一步取到中点」，链表取中点要走半条链，省下的比较全花在走链上，总时间仍是线性。

排除法：D D 选内存溢出的人编造了不存在的限制；A A 选无法比较大小的人没注意节点数据域照样可比；C C 选中间节点不存在的人想当然——中间节点存在，只是到不了。

考点：二分查找的局限（B8）。

（B8）考点：二分查找的局限——依赖有序性，预处理可能不划算；对重复元素照样可用。

解析：本题考查二分查找的局限。数据无序要先排序（$O(n\log_2 n)$），只查一次时不如直接扫；查得多次时排序一次反复受益。重复元素、小数、不存在的目标都能正确处理。

排除法：B B 以为只能查整数的人没见过浮点二分；C C 以为目标必须存在的人忘了失败返回 $-1$ 正是标准设计；D D 以为重复元素不行的人不了解边界变体正是为此而生。

考点：中点写法防溢出（C1）。

（C1）考点：中点写法防溢出——l + (r - l) / 2 与 (l + r) / 2 数学等价且不会溢出。

解析：本题考查中点写法防溢出。l、r 都接近 $21$ 亿时相加超出 int 上限，结果变负；先做减法差值很小，加回 l 不会越界。教学口径：两个写法算出的中点相同，差别只在安全性。

排除法：D D 以为更快的人把安全性优势错记成功效优势；B B 以为中点不同的人没推导过两式恒等；A A 以为自动上取整的人不知道整数除法始终向下取整，与写法无关。

考点：闭区间循环条件（C2）。

（C2）考点：闭区间循环条件——闭区间写法在 l <= r 时区间非空，仍需继续。

解析：本题考查闭区间循环条件。闭区间 [l, r] 在 l == r 时还剩一个元素没检查，必须再进一轮；写成 l < r 会漏判这最后一个候选。区间空（l > r）才是终止的充分条件。

排除法：C C 认为两条件等价的人在 l == r 处会漏元素；B B 认为少等号会死循环的人方向说反了——少等号是提前退出，多查才是死循环风险来源之一；D D 以为是为奇数长度服务的人把循环条件与取中点混为一谈。

考点：收缩时排除中点（C3）。

（C3）考点：收缩时排除中点——a[mid] 比较过就不再进候选，mid+1、mid-1 保证区间严格缩小。

解析：本题考查收缩时排除中点。既然已经确认 a[mid] 不是目标（或目标不在其一侧），把 mid 留在区间里只会白比一次甚至原地踏步；严格缩小也是循环必然终止的保证。

排除法：D D 以为缩得更快的人没注意两种写法每轮同样只缩小约一半；A A 以为编译错误的人知道得太少——l = mid 语法完全合法，坑在逻辑；C C 以为是习惯写法的人低估了它——不留 mid 正是防死循环的关键之一。

考点：查找失败返回负一（C4）。

（C4）考点：查找失败返回负一——$-1$ 不是合法下标，是标准的失败哨兵值。

解析：本题考查查找失败返回负一。合法下标从 $0$ 起，$-1$ 绝不会与真实位置撞车，调用方拿到 $-1$ 即知目标不存在。res 初值设 $-1$ 的用意相同。

排除法：D D 以为表示从末尾找的人把哨兵值误当成了方向；C C 以为表示成功的人把含义整个弄反；A A 以为是首下标的人忘了下标从 $0$ 不从 $-1$ 起。

考点：递归二分查找（C5）。

（C5）考点：递归二分查找——递归版以 l > r 为终止条件，每层只在半边继续。

解析：本题考查递归二分查找。找 $11$：区间 $[0,4]$ 中点 $2$ 恰是 $11$，直接返回 $2$。递归版与迭代版是同一逻辑的两种组织方式，深度为 $O(\log_2 n)$，不会爆栈。

排除法：C C 答 $11$ 的人混淆了「下标」与「值」；A A 答 $-1$ 的人没算出中点首跳即命中；B B 答 $4$ 的人把数组末尾当成了答案。

考点：失败时区间交错（C6）。

（C6）考点：失败时区间交错——查找失败时 l 最终越过 r，输出 1 0。

解析：本题考查失败时区间交错。找不存在的 $5$：中点 $2$（值 $11$）偏大，r=1；中点 $0$（值 $3$）偏小，l=1；中点 $1$（值 $7$）偏大，r=0，l > r 退出。l 停在第一个大于目标的位置、r 停在最后一个小于目标的位置，交错即「夹缝」。

排除法：B B 答 0 5 的人以为区间不动；A A 答 2 1 的人追踪轮次错一格；C C 答 0 0 的人漏了最后一轮收缩。

考点：一次比较剩一半（C7）。

（C7）考点：一次比较剩一半——1000 个元素第一次比较后候选至多剩 500 个。

解析：本题考查一次比较剩一半。$1000$ 个候选与中点比较后，目标只可能在左半或右半之一，较大的一半是 $500$ 个（奇数个时中点本身被排除）。再看一轮剩 $250$ 个，直观看见对数收缩。

排除法：C C 答 $999$ 的人以为比较只能排除一个元素，那是顺序查找；A A 答 $250$ 的人少算了一轮；D D 答 $1000$ 的人以为比较不缩小范围。

考点：第一个等于的求法（D1）。

（D1）考点：第一个等于的求法——命中后记下位置继续向左压缩。

解析：本题考查第一个等于的求法。a[mid] == x 只说明找到一个，未必最靠前；把 r 挪到 mid - 1 继续在左侧找更早的命中，循环结束时的记录值就是第一个。这种「记下再压缩」是边界二分的通用骨架。

排除法：D D 选立即返回的人会被重复元素坑——中点可能落在重复段中间；A A 选向右找的人方向反了，越找越靠后；B B 选返回 $0$ 的人臆断了「第一个必在开头」。

考点：最后一个等于的求法（D2）。

（D2）考点：最后一个等于的求法——命中后记下位置继续向右压缩。

解析：本题考查最后一个等于的求法。与 D1 镜像：把 l 挪到 mid + 1 向右试探更晚的命中，记录值最终停在最后一个等于处。

排除法：D D 选立即返回的人同样会被重复段坑；C C 选向左找的人方向反了；B B 选返回长度减一的人以为目标必在末尾，纯属臆断。

考点：lower_bound 语义（D3）。

（D3）考点：lower_bound 语义——返回第一个大于等于 x 的位置。

解析：本题考查 lower_bound 语义。它是「第一个不小于」的分界点：x 存在时是首个等于处，不存在时是首个大于处，因此同时兼任「插入位置」。手写实现正是 J6 的 a[mid] >= x 收缩法。

排除法：A A 选第一个大于的人把它与 upper_bound 弄混，差一个等号；D D 选第一个等于的人在 x 不存在时无位置可返；C C 选最后一个小于的人方向完全反了。

考点：upper_bound 语义（D4）。

（D4）考点：upper_bound 语义——返回第一个大于 x 的位置。

解析：本题考查 upper_bound 语义。它越过所有等于 x 的元素，给出严格大于的分界；与 lower_bound 相减得到 x 的出现个数（D8 的基础）。

排除法：D D 选第一个大于等于的是 lower_bound 的语义；B B 选最后一个等于的人在 x 不存在时同样无位置可返；C C 选最后一个小于等于的人把开区间边界想反。

考点：上取整中点防死循环（D5）。

（D5）考点：上取整中点防死循环——l = mid 配 (l + r + 1) / 2，两元素区间时中点取右边。

解析：本题考查上取整中点防死循环。区间剩 $[l, l+1]$ 时，下取整中点恒为 $l$，若此时执行 l = mid 区间纹丝不动，死循环；加一后中点变 $l+1$，l = mid 必然推进。口诀：l = mid 配上取整，r = mid 配下取整。

排除法：C C 以为收缩更快的人没抓住要害——加一为的是不死循环而非性能；B B 以为更靠左的人正好说反，加一是向右偏；D D 以为抵除法误差的人不知道整数除法没有误差，只有截断方向。

考点：二分下标找首个满足（D6）。

（D6）考点：二分下标找首个满足——条件真假单调时，判断结果同样能把下标区间砍半。

解析：本题考查二分下标找首个满足。P(mid) 为假说明分界在右侧（左侧连 mid 都假），为真说明分界在 mid 或其左——每次判断淘汰一半下标，$\log_2 n$ 次锁定真假分界。lower_bound 是它 P(i) = (a[i] >= x) 的特例。

排除法：A A 以为任何条件都能二分的人没注意单调性是命根子，条件乱跳时判断不能淘汰任何一侧；B B 以为与条件真假无关的人只看到下标有序，却忘了淘汰依据来自条件；D D 以为不能找条件边界的人低估了这一框架的威力。

考点：插入位置的语义（D7）。

（D7）考点：插入位置的语义——保持有序的插入点等于第一个大于等于 x 的位置。

解析：本题考查插入位置的语义。插在该位置前面，左侧全部小于 x、右侧全部大于等于 x，有序得以保持；这正是 lower_bound 的位置。x 大于所有元素时该位置是末尾，同样成立。

排除法：A A 选数组末尾的人没考虑 x 较小应插在中间的情形；C C 选第一个小于 x 的位置的人插错了侧，会把 x 放到比它小的元素左边；D D 选正中的人把「插入」当成了「对半」。

考点：出现次数等于差值（D8）。

（D8）考点：出现次数等于差值——出现次数 = upper 位置减 lower 位置。

解析：本题考查出现次数等于差值。lower 停在第一个 $\geq x$、upper 停在第一个 $> x$，两位置之间的元素全部等于 $x$，长度恰为差值；x 不存在时两位置重合，差值为 $0$，公式依旧成立。O2 是它的完整代码。

排除法：D D 选 lower 减一的人在 x 不存在时会算出负数或错值；A A 选长度减 upper 的算出的是「大于 x 的元素个数」；C C 选无法算出的人没见过两次边界二分的组合拳。

考点：二分答案的定义（E1）。

（E1）考点：二分答案的定义——对答案取值范围二分，配判定函数锁定可行值。

解析：本题考查二分答案的定义。当「验证一个候选答案」比「直接构造答案」容易得多时，把候选范围当有序数组二分：判定可行就往更优方向试，不可行就退回来，对数轮收敛。

排除法：D D 选对下标二分的人描述的是普通二分查找；A A 选平均分两半相加的人编造了不存在的算法；B B 选随机猜两次的人完全脱离二分的确定性框架。

考点：单调性前提（E2）。

（E2）考点：单调性前提——可行性随答案取值单调变化，二分才有淘汰依据。

解析：本题考查单调性前提。「可行」与「不可行」在值域上各占连续的一段（如可行 | 不可行），判定一次就能淘汰半段值域；若可行集间断分布，判定结果无淘汰力，二分失效。

排除法：B B 以为答案必须是整数的人把「常为整数」当成了「必须」；A A 以为可行解唯一的人没想到恰恰是要在大量可行解中找最优；C C 以为范围不超过一百万的人把工程习惯当成了数学前提。

考点：基本框架（E3）。

（E3）考点：基本框架——求最大可行答案：可行则记录并向大试，不可行则回退。

解析：本题考查基本框架。check(mid) 为真说明 mid 可行，但要试探能不能更大，故 ans = mid; l = mid + 1；为假说明太大，r = mid - 1。循环结束 ans 即最大可行值。求最小可行答案则方向全部对称反转。

排除法：D D 选向更小试的人把「最大」的方向弄反，会收敛到下界；B B 选立即输出的人放弃了继续优化的机会；C C 选递归对半的人把二分答案与分治混为一谈。

考点：题目特征（E4）。

（E4）考点：题目特征——「最大的最小值 / 最小的最大值」加单调可行性是二分答案的信号。

解析：本题考查题目特征。这类问法天然定义了「候选值——可行性」的单调关系：把阈值调宽松（最短距离调小、切割边长调小）总更容易满足，于是可二分。看到该特征先想 check 怎么写。

排除法：A A 选求数组所有元素之和的人面对的是简单统计，没有阈值可行性的结构；C C 选判断字符串是否回文的人面对的是字符串性质判定，同样无单调候选值可言；B B 选输出数组全排列的人面对的是枚举问题，组合空间里没有「可行段分界」可二分。

考点：check 函数的作用（E5）。

（E5）考点：check 函数的作用——判定候选答案可行性，通常一次贪心或扫描完成。

解析：本题考查 check 函数的作用。二分答案把「求最优」拆成「验证给定的值行不行」：check 内部往往是一个线性扫描的贪心（数够不够、截够不够），复杂度 $O(n)$；整体 $O(n\log_2 V)$。

排除法：B B 选计算最终答案的人弄反了分工——check 只判定不算最优；A A 选排序的人把预处理当成了判定；D D 选生成数据的人完全脱离语境。

考点：答案用 long long（E6）。

（E6）考点：答案用 long long——判定中的乘积或总和可能超出 int 范围。

解析：本题考查答案用 long long。mid 本身也许不大，但 mid * mid（K4 的平方判断）、总长度、总块数这类统计量轻易突破 $21$ 亿；答案变量与中间量一起开 long long 是稳妥习惯。

排除法：D D 以为更快的人把安全当成速度；B B 以为循环计数必须长整型的人混淆了不同的变量；C C 以为 int 不能比较的人夸大了限制——比较没问题，溢出才有问题。

考点：与二分查找的关系（E7）。

（E7）考点：与二分查找的关系——同一「砍一半」骨架，二分的对象从下标域换成答案值域。

解析：本题考查与二分查找的关系。二分查找在有序下标上找目标，二分答案在单调可行的值域上找最优，两者共享「判定一次淘汰一半」的灵魂；把「值域」看成「虚拟的有序数组」即可互相解释。

排除法：B B 选毫无共同点的人只见其形不见其神；C C 选多线程版本的人凭空发挥；A A 选必须先二分答案的人把依赖关系编反了——普通二分查找根本用不到二分答案。

考点：砍树问题模型（F1）。

（F1）考点：砍树问题模型——木材总量随砍伐高度单调不增，可二分高度。

解析：本题考查砍树问题模型。高度定得越高，每棵树截下的部分越短，总量只减不增；「总量 ≥ 需求」的可行性随之单调（低处全可行、高处全不可行），分界点即最高可行高度。check 是一次线性求和（L1）。

排除法：B B 以为总量与高度无关的人没算过高处截不到木材；A A 以为单调递增的人把方向想反，高度越高截得越多显然不真；C C 以为先增后减的人给虚构的形状硬安了二分不可行的结论——单调恰是二分的通行证。

考点：跳石头问题模型（F2）。

（F2）考点：跳石头问题模型——二分最短跳跃距离，距离越大需要移走的石头越多。

解析：本题考查跳石头问题模型。要求「任意相邻保留位置距离 ≥ mid」，mid 定得越大，被迫移走的石头越多，「移走数 ≤ M」的可行性单调递减，分界即最大可行距离。check 用一次贪心扫描（F7、L3）。

排除法：C C 选二分石头编号的人没注意编号不承载「距离阈值—可行性」的单调关系；B B 选石头总块数的人把约束条件当成了二分对象；D D 选起终点长度的人混淆了常量与变量。

考点：分巧克力问题模型（F3）。

（F3）考点：分巧克力问题模型——总份数随切割边长单调不增。

解析：本题考查分巧克力问题模型。边长越大，每块能切出的 $(w/x)\times(h/x)$ 份数越少，总份数单调不增；「份数 ≥ K」的可行段在左侧，分界即最大边长。check 是逐块求和（L4）。

排除法：C C 选单调递增的人方向反了，边长越大越切不出份数；A A 选保持不变的人没注意每块边长一旦不够整除份数直接掉零；D D 选先增后减的人同样虚构了非单调形状。

考点：单调函数最大值（F4）。

（F4）考点：单调函数最大值——条件真假单调变化，分界点即答案。

解析：本题考查单调函数最大值。mid * mid <= 30 在 $5$ 处为真、$6$ 处为假，真假分界就是最大满足值 $5$（L5 实测）。整数平方根（K4）同骨架：mid * mid <= n 找最大的 mid。

排除法：D D 以为任何不等式都能二分的人忽略了必须一侧恒真一侧恒假；A A 以为 $30$ 是 2 的幂才行的给前提加了不存在的条件；C C 以为满足的值唯一的人没想到 $0$ 到 $5$ 都满足，要的是其中最大的。

考点：ans 记录法（F5）。

（F5）考点：ans 记录法——可行即记录并继续向优，循环结束 ans 即最优可行值。

解析：本题考查 ans 记录法。求最大值方向：每次可行都记 ans = mid 再右推，之后即便全不可行，ans 保留着最后（也是最大）的可行值。它是二分答案框架里防「收敛点不是可行点」的保险。

排除法：D D 选清零重来的人没注意记录的正是要留的东西；B B 选标记失败的人把成功分支的语义弄反；C C 选提前退出的人放弃了继续向优的机会，得到的不是最大可行值。

考点：上界的设定（F6）。

（F6）考点：上界的设定——右界取所有树高的最大值，再高截不到任何木材。

解析：本题考查上界的设定。砍伐高度超过最高的树时一根木材都得不到，必然不可行，再大的候选毫无意义；取「最大树高」既不漏解又最小化二分轮数。下界通常取 $0$。

排除法：B B 选树高之和的人把「高度」与「总量」量纲弄混；D D 选需求量的人把约束当成了范围；A A 选棵数的人同样量纲错位——上界要罩住的是高度取值。

考点：check 里的贪心统计（F7）。

（F7）考点：check 里的贪心统计——一次线性扫描，能不移就不移，使移走数最少。

解析：本题考查 check 里的贪心统计。判定 mid 是否可行时从左到右扫：与上一保留位置距离不足 mid 的石头必须移走，其余保留——这样移走数最少；若最少的移走数都不超过 M，则可行。贪心的正确性来自「保留越早越给后面留余地」。

排除法：A A 选动态规划的人高估了判定难度，线性贪心足够；D D 选排序算法的人把预处理当成了判定本体；B B 选递归回溯的人没注意到判定不需要枚举方案，只要最优计数。

考点：实数二分求平方根（G1）。

（G1）考点：实数二分求平方根——平方不超过 2 随取值增大由真变假，根在分界。

解析：本题考查实数二分求平方根。区间 $[0,2]$，中点平方小于等于 $2$ 就把左端推过去，否则右端退回来，每轮根被夹在宽度减半的区间里（M1 是前三轮的实测）。2022 年阅读真题正是这一模型叠加迭代加细。

排除法：C C 以为 $2$ 是质数才能这样二分的人给前提加了无关条件，任何正实数都同理；A A 以为区间端点是整数才行的没注意端点第二轮起就是小数；B B 以为平方不改变单调方向的人恰恰说反了——$x^2$ 递增正是「真变假」单调性的来源，正是它能二分。

考点：精度终止条件（G2）。

（G2）考点：精度终止条件——区间宽度小于 eps 时两端皆可作为近似答案。

解析：本题考查精度终止条件。浮点没有「恰好相等」可指望，改为把答案夹进足够窄的区间：r - l > 1e-6 继续缩，停止时 $l$、$r$ 相差不足精度要求，输出任一端（或中点）误差可控。

排除法：B B 以为答案恰等于中点的人不了解停止时中点只是近似；A A 以为固定次数的人描述的是另一种等价写法（G3）；D D 以为答案是整数的人没注意这是浮点二分。

考点：固定次数迭代（G3）。

（G3）考点：固定次数迭代——一百轮减半后区间宽度小于任何实际需要的精度。

解析：本题考查固定次数迭代。初始宽度再大，$100$ 轮后宽度除以 $2^{100}$，远小于任何输出精度要求；用固定次数代替浮点比较，回避了 eps 选得不好导致的边界纠缠，是竞赛常用等价写法。

排除法：C C 以为一百次后变精确值的人夸大了迭代效果，仍是近似；B B 以为与溢出有关的人把两个不相干的问题扯在一起；D D 以为要输出一百位的人没注意题目精度通常只要求几位小数。

考点：二分求方程根（G4）。

（G4）考点：二分求方程根——两端函数值异号保证根在区间内，按中点符号收缩。

解析：本题考查二分求方程根。连续函数在 $f(l)$、$f(r)$ 异号时必穿越零点；取中点，其符号与哪端相同就把该端移到中点，根始终被夹在异号区间内（M3 用 $x^3-3$ 实测四轮）。

排除法：C C 选同号的人不知道同号不保证有根，二分无从谈起；B B 选都为零的人把特殊情况当成了前提；A A 选都是正数的人同样丢失了根存在的保证。

考点：浮点输出精度（G5）。

（G5）考点：浮点输出精度——eps 要比输出精度小，防四舍五入错位。

解析：本题考查浮点输出精度。输出三位小数时，若答案近似值与真值相差半分位以上，四舍五入可能差一位；把 eps 取到 $10^{-6}$，误差远小于 $0.0005$ 的半分位阈值，输出才稳。

排除法：C C 以为 eps 越大越慢的人把大小与快慢的因果关系记反——eps 越大停得越早；A A 以为输出位数由 eps 决定的人不知道输出位数由格式控制，eps 只保准确性；B B 以为浮点存不了三位小数的人夸大了浮点的局限。

考点：浮点二分起点（G6）。

（G6）考点：浮点二分起点——右界取 max(x, 1)，覆盖 0 到 1 之间开方变大的情形。

解析：本题考查浮点二分起点。$0<x<1$ 时 $\sqrt{x} > x$，若右界只取 $x$，根被排除在区间外，二分永远夹不到根；右界至少取 $1$（$\sqrt{1}=1$ 是分水岭）才能覆盖所有正实数。

排除法：A A 选 $2x$ 的人在 $x$ 极小（如 $10^{-9}$）时 $2x$ 仍小于根，区间照样不含根；D D 选 $x/2$ 的人把右界改得更小，错上加错；C C 选 $x^2$ 的人在 $x<1$ 时 $x^2$ 比 $x$ 还小，同样失效。

考点：每次排除一半的原因（H1）。

（H1）考点：每次排除一半的原因——有序给出方向判断，随机访问给出常数取中点。

解析：本题考查每次排除一半的原因。有序让「中点偏小/偏大」直接翻译成「目标在右/左」；随机访问让取中点是一步到位的 $O(1)$。两者合起来才有「比较一次、安全丢弃一半」。

排除法：D D 选元素互不相同与长度为偶数的人加错了前提，重复与奇数长度无妨；A A 选目标一定存在的忘了失败情形同样每轮减半；B B 选不允许重复的人与 H 的正确口径相反——重复元素恰是边界变体的用武之地。

考点：对数规模估算（H2）。

（H2）考点：对数规模估算——百万元素二分最多约 20 次。

解析：本题考查对数规模估算。$2^{20}=1048576>100$ 万，二十次减半足以把百万候选缩到一到两个；每翻十倍元素只多三四次比较，这是对数的从容。

排除法：C C 答 $100$ 次的人把对数量级当成了百分位；A A 答 $1000$ 次的人高估了三个数量级；D D 答 $50$ 万的人把顺序查找的最坏次数错安到二分头上。

考点：单次查找的选择（H3）。

（H3）考点：单次查找的选择——只查一次时排序不划算，直接顺序扫描。

解析：本题考查单次查找的选择。排序要 $O(n\log_2 n)$，一次顺序扫描只要 $O(n)$；为一次查询先付排序成本是「杀鸡用牛刀且刀钱更贵」。查的次数多起来后，排序一次的成本才能被摊薄。

排除法：B B 以为顺序一定更快的人没注意多次查询时二分摊销更优；C C 以为排序会破坏数据的人混淆了重排与破坏——数据还在，只是有序了；A A 以为二分不能用在有序数组上的人把前提说反了。

考点：多次查询的选择（H4）。

（H4）考点：多次查询的选择——排序一次，之后每次二分对数代价。

解析：本题考查多次查询的选择。上万次查询若每次顺序扫描要 $O(nq)$；先花 $O(n\log_2 n)$ 排序，之后每次 $O(\log_2 n)$，总量 $O((n+q)\log_2 n)$ 远小。O1 是「排序后二分」的代码形态。

排除法：C C 选每次顺序扫描的人在多次查询下代价线性叠加；B B 选每次先打乱的人不但无益反而破坏可二分性；A A 选打印人工找的人脱离了算法讨论。

考点：折半最大比较次数（H5）。

（H5）考点：折半最大比较次数——n 个元素最大比较 ⌊log₂n⌋+1 次。

解析：本题考查折半最大比较次数。$100$ 个元素：$2^6=64<100\leq 2^7=128$，最坏走满 $7$ 层。口诀「向下取整加一」；$1000$ 个元素同法得 $10$ 次。此考法在近年真题中两次出现，值得背熟推法。

排除法：A A 答 $10$ 的人可能照搬了 $1000$ 元素的答案，没按本题 $100$ 元素重算；B B 答 $6$ 的人只取了 $\log_2 100$ 的整数部分漏加一；D D 答 $50$ 的人把顺序查找一半的量级错安过来。

考点：顺序查找输出下标（I1）。

（I1）考点：顺序查找输出下标——带 break 的扫描输出第一个匹配下标。

解析：本题考查顺序查找输出下标。$7$ 在下标 $1$ 首先命中，break 立即停住，输出 $1$；后面下标 $3$ 的 $7$ 不再看。break 保证「最早命中」语义。

排除法：C C 答 $3$ 的人忽略了 break，以为会扫完取最后；A A 答 $7$ 的人混淆了下标与值；D D 答 $-1$ 的人没看到首个元素就命中不了——第二个元素就是 $7$。

考点：查找失败返回负一（I2）。

（I2）考点：查找失败返回负一——目标不存在时 pos 保持初值 $-1$。

解析：本题考查查找失败返回负一。$9$ 不在数组中，五轮比较全落空，pos 从未被赋值，保持 $-1$ 输出。这题同时提醒：无 break 的循环扫完整个数组也一无所获。

排除法：D D 答 $0$ 的人以为失败返回首下标；B B 答 $4$ 的人把「扫到最后」误当「返回最后下标」；C C 答 $9$ 的人输出成了查找目标本身。

考点：统计出现次数（I3）。

（I3）考点：统计出现次数——不 break 的顺序扫描逐个计数。

解析：本题考查统计出现次数。$2$ 出现在下标 $0$、$2$、$4$ 共 $3$ 处，循环必须走完全程，输出 $3$。计数场景 break 反而漏计。

排除法：B B 答 $1$ 的人以为命中一次就完事；C C 答 $6$ 的人把数组长度当成了次数；D D 答 $2$ 的人漏数了中间那个 $2$。

考点：不停时取最后匹配（I4）。

（I4）考点：不停时取最后匹配——无 break 的循环每次命中覆盖 pos，留下最后一个。

解析：本题考查不停时取最后匹配。$6$ 在下标 $0$、$2$、$3$ 出现，最后覆盖发生在下标 $3$，输出 $3$。有无 break 决定「第一个」还是「最后一个」，一字之差语义全变。

排除法：A A 答 $0$ 的人按 break 的语义理解了无 break 的代码；B B 答 $-1$ 的人没看到数组里有 $6$；C C 答 $6$ 的人又把值当下标输出。

考点：打擂台找最大位置（I5）。

（I5）考点：打擂台找最大位置——严格大于才换擂主，并列保留最先。

解析：本题考查打擂台找最大位置。$9$ 在下标 $1$ 与 $3$ 并列最大，a[i] > a[k] 是严格大于，下标 $3$ 的 $9$ 不再换擂，输出 1 9。若想取最后一个最大值要改成 >=。

排除法：D D 答 3 9 的人默认了并列换擂，严格比较恰恰不换；B B 答 1 5 的人输出的擂主初值是首元素旧值，擂台在第一轮就换成了 $9$；C C 答 4 9 的人臆断了数组末尾，末元素是 $4$ 上不了擂。

考点：标准二分执行（J1）。

（J1）考点：标准二分执行——追踪三轮锁定下标 5。

解析：本题考查标准二分执行。找 $23$：区间 $[0,9]$ 中点 $4$（值 $16<23$）推左界到 $5$；区间 $[5,9]$ 中点 $7$（值 $56>23$）退右界到 $6$；区间 $[5,6]$ 中点 $5$（值 $23$）命中，输出 $5$。

排除法：A A 答 $23$ 的人输出成了元素值而非下标；D D 答 $4$ 的人停在第一轮中点没继续收缩；B B 答 $-1$ 的人没追踪完，$23$ 就在数组里。

考点：二分失败执行（J2）。

（J2）考点：二分失败执行——目标不存在时区间交错退出，返回初值 $-1$。

解析：本题考查二分失败执行。找 $24$：中点 $4$（$16<24$）左界推到 $5$；中点 $7$（$56>24$）右界退到 $6$；中点 $5$（$23<24$）左界推到 $6$；中点 $6$（$38>24$）右界退到 $5$，l > r 退出，输出 $-1$。

排除法：D D 答 $5$ 的人停在中间某一轮以为会命中；B B 答 $6$ 的人把最后的交错界当成了答案下标；A A 答 $0$ 的人以为失败返回首下标。

考点：降序数组二分（J3）。

（J3）考点：降序数组二分——收缩方向随有序方向反转。

解析：本题考查降序数组二分。降序中「更大」在左侧：找 $72$，中点 $4$（值 $23<72$）说明目标在左侧，退右界到 $3$；中点 $1$（值 $72$）命中，输出 $1$。方向反了就全盘皆错（P3）。

排除法：B B 答 $8$ 的人按升序方向收缩走进了死胡同；C C 答 $-1$ 的人方向反了自然找不到；D D 答 $72$ 的人又是值与下标不分。

考点：输出中点序列（J4）。

（J4）考点：输出中点序列——每轮中点依次是 3、5、6、7。

解析：本题考查输出中点序列。找末元素 $15$：中点 $3$（$7<15$）左界到 $4$；中点 $5$（$11<15$）左界到 $6$；中点 $6$（$13<15$）左界到 $7$；中点 $7$（$15$）命中。输出连起来是 3567。找末元素时中点一路右挪，是对数收缩的直观样子。

排除法：B B 答 367 的人漏了首轮的 $3$；A A 答 35 的人以为两轮就停；C C 答 7 的人以为一步就猜中末尾。

考点：比较次数统计（J5）。

（J5）考点：比较次数统计——找末元素恰好走了 4 轮。

解析：本题考查比较次数统计。找 $91$：中点 $4\to7\to8\to9$，前三轮都偏小推左界，第四轮中点 $9$ 恰是 $91$，cnt 停在 $4$。十个元素的查找最多也就四轮，印证 $\log_2 10\approx 3.3$ 向上取整。

排除法：A A 答 $10$ 的人把顺序查找的次数错安过来；C C 答 $1$ 的人以为一步命中；D D 答 $2$ 的人低估了收缩轮数——$10$ 缩到 $1$ 至少要四步中的三步外加命中一步。

考点：手写 lower_bound（J6）。

（J6）考点：手写 lower_bound——第一个大于等于 7 的位置是 4。

解析：本题考查手写 lower_bound。a[mid] >= x 为真就退右界（答案在 mid 或更左），假就推左界；收敛在 $4$，值 $7$，输出 4 7。三个连续 $7$ 中它精准停在最前面那个。

排除法：C C 答 6 7 的人停到了重复段的中间或末尾，等号方向没扣准；B B 答 7 9 的人做成了 upper_bound；D D 答 3 5 的人收缩方向反了停进了左侧。

考点：手写 upper_bound（J7）。

（J7）考点：手写 upper_bound——第一个大于 7 的位置是 7。

解析：本题考查手写 upper_bound。a[mid] > x 为真退右界，假（含等于）推左界；连续的 $7$ 全被「等于也推左」跳过，收敛在下标 $7$（值 $9$），输出 7 9。与 J6 一对比，「差一个等号」的语义立现。

排除法：B B 答 6 7 的人停在最后一个 $7$，把 upper 当成了「最后一个等于」；C C 答 4 7 的人做成了 lower_bound；A A 答 8 9 的人越过了第一个大于位置，$r$ 初值 $8$ 本身不可达。

考点：第一次出现位置（K1）。

（K1）考点：第一次出现位置——lower_bound 收敛后再判等，得首个等于的下标。

解析：本题考查第一次出现位置。a[mid] >= 4 的收缩收敛在下标 $1$——第一个不小于 $4$ 处，恰是首个 $4$；末尾 a[l] == x 再确认存在性，存在输出 $1$，否则 $-1$。

排除法：B B 答 $3$ 的人停到了重复段末尾，等号方向没扣准；C C 答 $2$ 的人收缩方向反了；A A 答 $-1$ 的人没看到数组里明明有 $4$。

考点：最后一次出现位置（K2）。

（K2）考点：最后一次出现位置——先找第一个大于 x 的位置，减一即最后一个等于。

解析：本题考查最后一次出现位置。a[mid] <= 4 推左界的写法收敛在「第一个大于 $4$」的位置 $4$（值 $6$），$l-1=3$ 正是最后一个 $4$。「upper 减一」与「上取整中点」（K6）是同一目标的两种路线。

排除法：B B 答 $1$ 的人给成了第一个 $4$，把边界目标弄反；A A 答 $4$ 的人忘了减一，停在了大于处；D D 答 $2$ 的人停在重复段中间。

考点：插入位置（K3）。

（K3）考点：插入位置——第一个大于等于 6 的位置即保序插入点。

解析：本题考查插入位置。>= 6 的收缩停在下标 $3$（值 $7$），$6$ 插在它前面，左侧 $\{1,3,5\}$ 全小、右侧 $\{7,9\}$ 全大，有序保持——插入点语义与 lower_bound 重合（D7）。

排除法：C C 答 $2$ 的人把 $6$ 插到 $5$ 前面打乱了序；A A 答 $4$ 的人把插入点挪到 $7$ 后面同样乱序；D D 答 $6$ 的人把元素的值当下标。

考点：整数平方根（K4）。

（K4）考点：整数平方根——值域上二分找最大的 mid 使平方不超过 n。

解析：本题考查整数平方根。mid*mid <= 40 在 $6$ 处真、$7$ 处假，ans 最终记下 $6$（$36\leq40<49$）。这是二分答案骨架在「值域」上的最小样例，变量用 long long 防 mid*mid 溢出（E6）。

排除法：C C 答 $7$ 的人把「四舍五入到最接近的平方根」当成了目标，二分找的是整数下取整根；B B 答 $5$ 的人少试探了一步；D D 答 $36$ 的人把 $6$ 的平方当成了答案输出。

考点：中点溢出的风险（K5）。

（K5）考点：中点溢出的风险——两数之和超 int 上限变负，中点跟着错。

解析：本题考查中点溢出的风险。$2000000000+2100000000=4.1\times10^9$，超出约 $2.15\times10^9$ 的 int 上限，加法结果回绕为负，除以 $2$ 后 mid 仍是负数，用作下标立即越界。防御写法 l+(r-l)/2（C1）。

排除法：A A 以为 mid 变 $0$ 的人没推过回绕后的数值；D D 以为自动升级 long long 的人高估了编译器——int+int 就是 int；B B 以为 int 存任意大数的人不了解定长整型的硬边界。

考点：上取整中点执行（K6）。

（K6）考点：上取整中点执行——加一取中配 l = mid，安全找到最后一个 2。

解析：本题考查上取整中点执行。找最后一个 $\leq2$：区间 $[0,4]$ 中点 $(0+4+1)/2=2$（值 $2$）l=2；区间 $[2,4]$ 中点 $3$（值 $2$）l=3；区间 $[3,4]$ 中点 $4$（值 $5$）r=3，收敛输出 3 2。加一让两元素区间时中点落在右侧，l=mid 也能推进。

排除法：B B 答 1 2 的人给的是第一个 $2$，目标弄反；A A 答 4 5 的人越过了 $5$ 这个不满足的元素；C C 答 2 2 的人停在了重复段中间，没压到最右。