第 12 章 查找 · 知识细节练习

考点：顺序查找的定义（A1）。

解析：顺序查找（线性查找）= 从第一个元素开始逐个与目标比较，找到即停，查完还没找到就是"不存在"。✅ 正确

排除法：无（判断题）。混淆点：顺序查找不需要数据有序，这是它与二分查找最大的前提差异（B2）。

关联 · 顺序查找的适用场景（A2）：无序数据只能用顺序查找——这是它不可替代的原因。

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

解析：三种典型场景：① 数据无序；② 数据量小（$O(n)$ 也很快）；③ 存储在链表等无随机访问的结构上（A6）。✅ 正确

排除法：无（判断题）。混淆点：数据有序且大时顺序查找就吃亏了，改用二分（B5）。

关联 · 链表只能顺序查找（A6）：链表不能下标跳转，顺序查找是唯一选择。

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

解析：最坏 = 目标在最后一个位置或不在数组里：要把 $n$ 个元素全部比较一遍，共 $n$ 次。正确答案 B。

排除法：A（$n/2$ 次）是"成功查找的平均次数"（A4）；C（$\log_2 n$）是二分查找的复杂度；D（$1$ 次）是最佳情况（第一个就是）。

关联 · 成功查找的平均比较次数（A4）：最坏与平均是两个概念，别混。

考点：成功查找的平均比较次数（A4）。

解析：目标在每个位置等概率时，比较次数为 $1, 2, \dots, n$，平均 $(1 + 2 + \cdots + n) / n = (n+1)/2 \approx n/2$。正确答案 A。

排除法：B（$n$ 次）是最坏情况；C（$\log_2 n$）是二分复杂度；D（$n^2$）不可能是线性扫描的量级。

关联 · 顺序查找最坏比较次数（A3）：平均 $n/2$、最坏 $n$，都是 $O(n)$ 级别。

考点：数组下标从 0 开始（A5）。

解析：C++ 数组下标 $0 \sim n-1$：a[0] 是第一个元素，for (int i = 0; i < n; i++) 恰好访问全部 $n$ 个元素。✅ 正确

排除法：无（判断题）。混淆点：边界写 i <= n 会访问 a[n] 越界（P3 同源错误）。

关联 · 查找失败的返回值（G3）：下标从 0 开始，所以"找不到"常用 -1 而不是 0。

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

解析：链表只能通过指针从头向后逐个走（无随机访问），因此查找必须顺序进行：$O(n)$。✅ 正确

排除法：无（判断题）。混淆点：链表上"二分"无从谈起——取不到中点（B7）。

关联 · 链表不能高效二分（B7）：二分需要 $O(1)$ 跳到中间元素，链表做不到。

考点：顺序查找与二分查找的前提（A7）。

解析：二分查找的前提是数据有序；顺序查找无此要求。正确答案 C。

排除法：A 说反（二分恰恰要求有序）；B 说反（顺序查找不要求有序）；D 张冠李戴（$O(\log_2 n)$ 是二分的复杂度，顺序是 $O(n)$）。

关联 · 二分查找的前提条件（B2）：有序是二分成立的地基。

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

解析：每次取区间中点与目标比较，根据大小关系把区间砍掉一半，重复直到找到或区间为空——典型的分治思想。✅ 正确

排除法：无（判断题）。混淆点："砍一半"靠的是有序：中点一边全小、另一边全大（B2）。

关联 · 每次排除一半的原因（F1）：规模每次减半 → $O(\log_2 n)$。

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

解析：数组必须有序（升序或降序均可，比较方向相反而已）。正确答案 B。

排除法：A 说反；C（元素互不相同）不必要——有重复也能二分（C4/C5）；D（个数偶数）不必要——任何 $n$ 都能二分。

关联 · 降序数组的二分（G2）：降序时收缩方向翻转。

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

解析：升序数组里 a[mid] < x 说明 x 只可能在右侧（更大的那边），区间收缩为 [mid + 1, r]。正确答案 B。

排除法：A 方向反（左侧元素更小，不可能有 x）；C 是找到时才做的动作；D 是查完区间为空时的结论。

关联 · 收缩时排除 mid（C3）：mid 已经比较过，收缩必须把它排除。

考点：二分查找的比较次数（B4）。

解析：每次砍半，$1000$ 个数最多 $10$ 次比较就剩 $1$ 个（$2^{10} = 1024 \geq 1000$）。正确答案 A。

排除法：B（$100$ 次）是 $n/10$ 量级的误解；C（$500$ 次）是顺序查找的平均次数（A4）；D（$1000$ 次）是顺序查找的最坏次数（A3）。

关联 · 对数规模的估算（F2）：$10^6 \to 20$ 次、$10^9 \to 30$ 次，同款估算。

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

解析：$n = 10^6$ 时二分最多约 $\log_2 10^6 \approx 20$ 次比较，顺序平均约 $5 \times 10^5$ 次——差距约 25000 倍。✅ 正确

排除法：无（判断题）。混淆点：这个优势只在"有序 + 多次查找"时兑现（F3/F4）。

关联 · 两种查找的比较次数对比（F6）：$n$ 越大，差距越悬殊。

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

解析：二分 = 对单调的判断条件收缩可行区间：数组有序 → "在左/右"可判定；答案可行性单调 → "取 mid 可行/不可行"可判定。两者同源。✅ 正确

排除法：无（判断题）。混淆点：以为二分只能查数组——二分答案（D1）就是它的推广。

关联 · 二分答案的定义（D1）：把"下标区间"换成"答案区间"。

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

解析：二分每步要 $O(1)$ 取中点，链表取中点要 $O(n)$ 遍历——整体退化回 $O(n)$，与顺序查找相当，失去二分意义。❌ 错误（原句说法错误）

排除法：无（判断题）。混淆点："向后走一半距离"本身就要 $O(n)$ 步，每次砍半的收益被走路成本吃掉。

关联 · 二分查找的局限（F5）：有序 + 随机访问，两个条件缺一不可。

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

解析：l + (r - l) / 2 先算区间长度（不溢出）再折半，是标准写法；(l + r) / 2 在 l、r 接近 $2^{31} - 1$ 时加法溢出。正确答案 B。

排除法：A 是易错写法（H2/K1/P2 的祸根）；C 把除 2 写成乘 2，完全错误；D l/2 + r/2 在两者皆奇数时会少 1。

关联 · 中点加法的溢出（H2）：$2 \times 10^9$ 级别相加即溢出。

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

解析：闭区间 [l, r] 中 l == r 时还剩 $1$ 个元素，必须再检查一次，所以条件是 l <= r。✅ 正确

排除法：无（判断题）。混淆点：左闭右开 [l, r) 才用 l < r（J6/J7），两套写法要配套使用（P3）。

关联 · 区间开闭不统一（P3）：闭区间配 < 或开区间配 <= 都会出问题。

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

解析：mid 已比较过，a[mid] > x 时 x 在 [l, mid - 1]；同理 a[mid] < x 时在 [mid + 1, r]。正确答案 B。

排除法：A 方向反；C（[l, mid]）没排除 mid，等于白比较一次、可能死循环（H3）；D 无意义。

关联 · 收缩方向写错（H3）：不排除 mid 是二分最常见的 bug。

考点：找第一个等于 x 的位置（C4）。

解析：有重复元素时，普通二分命中的"等于 x"位置不保证是第一个；要找第一个，命中后继续向左收缩（r = mid - 1 并记录 ans）。✅ 正确

排除法：无（判断题）。混淆点：lower_bound（第一个 $\geq x$）能直接定位第一个等于 x 的位置（C6）。

关联 · 第一次出现的位置（K4）：a[mid] >= x 时记 ans 并 r = mid - 1。

考点：找最后一个等于 x 的位置（C5）。

解析：数组 {1, 2, 2, 2, 3, 3, 5} 中等于 $2$ 的下标是 $1, 2, 3$，最后一个是下标 $3$。正确答案 C。

排除法：A（$1$）是第一个；B（$2$）是中间那个；D（$4$）是 $3$ 第一次出现的位置。

关联 · 最后一次出现的位置（K5）：命中等值时向右收缩。

考点：lower_bound 的概念（C6）。

解析：lower_bound = 第一个大于等于 x 的位置。{1, 3, 3, 5, 7, 9} 中 $\geq 4$ 的第一个是 $5$（$3$ 都小于 $4$）。正确答案 C。

排除法：A（$3$）小于 $4$ 不满足；B（$4$）数组里没有，答案必须是数组元素；D（$7$）不是"第一个"。

关联 · upper_bound 的概念（C7）：只差一个等号：$\geq x$ 与 $> x$。

考点：upper_bound 的概念（C7）。

解析：upper_bound = 第一个大于 x 的位置。{1, 3, 3, 5, 7, 9} 中 $> 3$ 的第一个是 $5$（两个 $3$ 都不大于 $3$）。正确答案 C。

排除法：A（$1$）小于 $3$；B（$3$）不大于 $3$；D（$9$）不是"第一个"。

关联 · 二分统计出现次数（O2）：upper_bound - lower_bound = 出现次数。

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

解析：答案的取值范围已知、可行性随答案单调时，对答案二分：check(mid) 判"答案取 mid 是否可行"，可行/不可行各砍掉一半区间。✅ 正确

排除法：无（判断题）。混淆点：二分答案的复杂度是 $O(\log R \times \text{check})$，check 内部还要跑一遍 $O(n)$ 或贪心。

关联 · 二分答案的基本框架（D3）：主循环就三种写法，背熟一种。

考点：二分答案的单调性前提（D2）。

解析：可行性必须随答案单调：例如"砍到 H 得木材 ≥ M"，H 越小越容易可行——可行/不可行各成一段，二分才找得到分界点。✅ 正确

排除法：无（判断题）。混淆点：没有单调性的问题（可行性忽真忽假）二分会漏解或错解。

关联 · 砍树问题的单调性（E1）：木材量随 H 单调递减。

考点：二分答案的基本框架（D3）。

解析：求最大可行答案：可行时 mid 要保留 → l = mid；mid 向下取整会让区间卡死，所以中点用 (l + r + 1) / 2。正确答案 A。

排除法：B 是"最小可行答案"的框架（可行 r = mid、中点向下取整）；C 是枚举不是二分；D 没有利用单调性。

关联 · 死循环：l 与 mid 的关系（H1）：l = mid 配向下取整 = 死循环。

考点：二分答案的题目特征（D4）。

解析："最小的最大值 / 最大的最小值"类最优化问题（砍树求最大高度、跳石头求最大最小间距），答案越界可行/不可行单调，是二分答案的主场。正确答案 B。

排除法：A、C 一次扫描/累加即可，不必二分；D 与二分无关。

关联 · 跳石头问题模型（E2）：最小值最大化 → 最大可行答案框架。

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

解析：check(mid) = 判断"答案取 mid 能否满足限制"。可行 → mid 留在区间内继续试探；不可行 → mid 及更差的一半全部排除。✅ 正确

排除法：无（判断题）。混淆点：check 写得越高效，二分答案总时间越少——它内部常是贪心或模拟（E6）。

关联 · check 内部的贪心验证（E6）：验证"最短间距 ≥ mid"用贪心数移走的石头。

考点：二分答案的数据类型（D6）。

解析：答案可达 $10^9$ 以上时，l + r、mid 运算、check 内求和都可能超出 int——统一用 long long 最稳妥。✅ 正确

排除法：无（判断题）。混淆点：CSP-J 二分答案题常卡 int 溢出（例如砍树求和 $n \times h$ 可达 $10^{14}$）。

关联 · 中点加法的溢出（H2）：(l + r) / 2 的溢出就是类型问题。

考点：二分答案与二分查找（D7）。

解析：二分查找在"下标区间"上二分（有序数组），二分答案在"答案取值区间"上二分（可行性单调）——思想相同、对象不同。✅ 正确

排除法：无（判断题）。混淆点：二分答案常借用二分查找的边界写法（上取整/下取整、开闭区间），坑也一样（H1/P3）。

关联 · 二分的本质是收缩区间（B6）：两种二分是同一个思想的两个应用。

考点：砍树问题的单调性（E1）。

解析：总木材 $= \sum \max(0, h_i - H)$。$H$ 减小 → 每棵树砍下的部分变多 → 总木材增加（单调递减函数）。正确答案 C。

排除法：A 方向反；B 只在个别树高恰好等于 $H$ 的瞬间不变；D 错——单调性是确定的。

关联 · 砍树二分答案（L1）：木材量单调 → 二分最大 $H$。

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

解析：目标是最小间距尽可能大 = 最小值最大化，典型的二分答案模型：check(mid) 数一数"间距 $\geq mid$ 需移走几块"，$\leq M$ 即可行。正确答案 A。

排除法：B（最大值最小化）是另一个方向的模型；C 与场景无关；D 贪心直接取最大间隔没有正确性保证——必须二分 + 验证。

关联 · 跳石头二分答案（L2）：贪心验证 + 二分主循环。

考点：分巧克力问题（E3）。

解析：每块 $h_i \times h_i$ 切 $\lfloor h_i / mid \rfloor^2$ 块。mid 变大 → 每块切得少 → 总数变少（单调递减）。正确答案 B。

排除法：A 方向反；C/D 忽略了整除的单调性。

关联 · 分巧克力二分答案（L3）：cnt(mid) >= K 找最大边长。

考点：浮点二分求平方根（E4）。

解析：$f(mid) = mid^2$ 单调递增，mid^2 <= 2 的"可行域"是 $[0, \sqrt{2}]$——把二分查找的框架套到实数上即可。✅ 正确

排除法：无（判断题）。混淆点：实数二分没有"相等"，靠精度或迭代次数终止（E5）。

关联 · 实数二分求平方根（M1）：60 次迭代足够精确到 15 位小数。

考点：浮点二分的终止条件（E5）。

解析：浮点几乎不会精确相等，标准写法是 while (r - l > eps)——区间长度 $\leq eps$ 时停止，误差不超过 $eps$。正确答案 B。

排除法：A（l == r）可能永远不成立；C（循环 $n$ 次）与数据个数无关；D 是二分查找的比较次数概念，不适用。

关联 · 固定次数迭代（M3）：不想调 eps 就固定迭代 50~100 次。

考点：check 内部的贪心验证（E6）。

解析：验证"最短间距能否 $\geq mid$"：从起点开始，遇到间距不够的石头就移走（贪心：移得越靠前留给后面越多），最后数移走数量 $\leq M$ 即可行。✅ 正确

排除法：无（判断题）。混淆点：贪心只在 check 内部做验证用，答案本身仍靠二分找。

关联 · 跳石头二分答案（L2）：cnt(mid) 就是这段贪心。

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

解析：二分每次比较排除一半元素：$n \to n/2 \to n/4 \to \cdots \to 1$，共约 $\log_2 n$ 步——这就是 $O(\log_2 n)$ 的来源。正确答案 A。

排除法：B（一次比较排除一个）是顺序查找的节奏，$O(n)$；C、D 与二分无关。

关联 · 二分查找的比较次数（B4）：$1000 \to 10$ 次、$10^9 \to 30$ 次。

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

解析：$2^{30} \approx 1.07 \times 10^9$，所以 $10^9$ 规模最多约 $30$ 次比较。正确答案 A。

排除法：B（$90$）是 $3\log$ 的误解；C/D 都是线性或平方量级，与二分无关。

关联 · 两种查找的比较次数对比（F6）：规模翻倍只多 1 次比较。

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

解析：只查 1 次时，排序 $O(n \log n)$ 是纯开销：直接顺序查找 $O(n)$ 更快。正确答案 B。

排除法：A 排序后二分总代价 $O(n \log n) > O(n)$；C 哈希建表也是 $O(n)$ 但常数大、小题大做；D 二分要求有序，无序时直接二分不可信（H4）。

关联 · 多次查找的选择（F4）：查询次数多时排序的一次性成本被摊薄。

考点：多次查找的选择（F4）。

解析：查询 $m$ 次（$m$ 大）：顺序查找 $O(mn)$；先排序 $O(n \log n)$ 再每次二分 $O(m \log n)$，$m$ 大时后者完胜。正确答案 B。

排除法：A 每次 $O(n)$ 总量 $O(mn)$ 太慢；C 每次查询都排序纯浪费；D 无正确性。

关联 · 排序后多次二分（O1）：sort 一次 + 循环内二分。

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

解析：二分要求有序 + 随机访问；数据频繁插入/删除时，每次维护有序都要移动 $O(n)$ 元素，此时平衡树/哈希更合适（CSP-J 只需理解局限即可）。✅ 正确

排除法：无（判断题）。混淆点：二分快是有代价的——代价就是"有序"这个前提。

关联 · 二分查找的前提条件（B2）：前提不满足，二分失效。

考点：两种查找的比较次数对比（F6）。

解析：$2^{20} \approx 10^6$，所以 $n = 10^6$ 时二分最坏约 $20$ 次；顺序平均约 $5 \times 10^5$ 次。正确答案 A。

排除法：B/C/D 分别是 $10^6$ 的 $10^{-4}$、$10^{-3}$、$10^{-2}$ 量级，都不是对数规模。

关联 · 二分与顺序的速度对比（B5）：$n$ 越大差距越大。

考点：lower_bound 与 upper_bound（G1）。

解析：lower_bound(a, a+n, x) 返回第一个 $\geq x$ 的位置（迭代器）；upper_bound 返回第一个 $> x$ 的位置。正确答案 B。

排除法：A 把"大于等于"缩成"等于"；C 是"最后一个小于"（等价 lower_bound - 1）；D 是"次数"（=upper - lower，O2）。

关联 · 二分统计出现次数（O2）：两者相减即出现次数。
大纲注：lower_bound/upper_bound 不在入门级 STL 白名单，属二分查找的常用工具。

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

解析：降序数组左大右小：a[mid] < 4 说明当前位置已小于 $4$，更大的在左侧（下标更小的方向）。正确答案 A。

排除法：B 是升序数组的方向（降序恰好相反）；C 草率——还要继续找；D 未比较完不能定论。

关联 · 降序数组的二分（J4）：收缩方向与升序完全相反。

考点：查找失败的返回值（G3）。

解析：下标从 $0$ 开始，$0$ 是合法下标，所以"找不到"必须用 $-1$ 之类的非法值，不能与合法下标冲突。✅ 正确

排除法：无（判断题）。混淆点：STL 的 lower_bound 找不到时返回"尾后"迭代器 a+n，与手写 $-1$ 是两种约定。

关联 · 数组下标从 0 开始（A5）：下标约定决定哨兵值的选择。

考点：二分也能求平方根（G4）。

解析：mid * mid <= x 的可行性随 mid 单调：在 $[0, x]$ 中找最大的 mid 满足 mid * mid <= x，即 $\lfloor \sqrt{x} \rfloor$。✅ 正确

排除法：无（判断题）。混淆点：mid * mid 要用 1LL 防溢出（K7）。

关联 · 二分求整数平方根（K7）：上取整中点 + l = mid 框架。

考点：递归与迭代写法（G5）。

解析：递归版（对半区间递归）与迭代版（while 循环）等价，复杂度都是 $O(\log_2 n)$；递归多一层函数调用开销。✅ 正确

排除法：无（判断题）。混淆点：递归版注意 l > r 为终止条件；迭代版注意循环条件与收缩配套（C2/C3）。

关联 · 递归二分查找（J5）：递归版代码示例。

考点：死循环：l 与 mid 的关系（H1）。

解析：mid = (l + r) / 2 向下取整，当 l = r - 1 时 mid == l；此时若 check 为真执行 l = mid，区间毫无变化 → 死循环。正确答案 A。

排除法：B/C 不是必然结论；D 错——这是求"最大可行"时最经典的 bug。

关联 · 二分答案的基本框架（D3）：l = mid 必须配 mid = (l + r + 1) / 2。

考点：中点加法的溢出（H2）。

解析：l + r 两个 $2 \times 10^9$ 级别的 int 相加超过 $2^{31} - 1 \approx 2.1 \times 10^9$，先溢出再除以 2，得到错误的（甚至负的）mid。正确答案 A。

排除法：B——C++ 不会自动升级，类型由操作数决定；C——能编译，运行时才溢出；D 错，见 K1 的实际输出。

关联 · 中点写法防溢出（C1）：l + (r - l) / 2 根治。

考点：收缩方向写错（H3）。

解析：a[mid] > x 时 mid 已排除，却写 l = mid：区间含着一个已比较过的位置，可能反复检查同一位置甚至死循环。正确答案 A。

排除法：B/C 说反——错误写法只会更慢或卡死；D 无保证。

关联 · 收缩时排除 mid（C3）：比较过的 mid 必须排除。

考点：无序数组不能二分（H4）。

解析：二分依赖"中点一边全小、一边全大"的判定，数组无序时该判定失效：可能碰巧查对，也可能查错——结果不可信。✅ 正确

排除法：无（判断题）。混淆点：不是"一定找不到"，而是"不可信"，这是两回事。

关联 · 单次查找的选择（F3）：无序就先顺序查找，或先排序再二分。

考点：check 方向写反（H5）。

解析：求最大可行答案时，check(mid) 为真应保留 mid（l = mid）；写反成 r = mid - 1 把可行解丢掉，最终答案偏小甚至取到下界。正确答案 A。

排除法：B 偏大是另一种写反；C 不是必然；D 错——这是二分答案最隐蔽的 bug 之一。

关联 · check 方向写反（P5）：代码实证——条件反了答案冲到上界。

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

解析：从头扫：$3 \neq 9$、$7 \neq 9$、$1 \neq 9$、$a[3] = 9$ 命中 → 输出下标 3 并 break。正确答案 A。

实现要点：顺序查找 = for 扫描 + 命中即停（break）。输出的是下标不是值——i 与 a[i] 要分清（O5 同款考点）。

排除法：B（4）把命中位置记错；C（9）输出的是值不是下标；D（2）是 a[5] 的值。

关联 · 找第一个匹配的下标（I4）：从左往右扫，天然找到第一个。

考点：查找失败返回 -1（I2）。

解析：$4$ 不在数组里，循环跑完 pos 仍是初值 -1，输出 -1。正确答案 A。

实现要点：找不到的约定：pos 初值设 -1，扫完没更新就返回 -1。$-1$ 不会与合法下标 $0 \sim 4$ 冲突。

排除法：B（0）会把"下标 0"与"找不到"混淆；C（4）是最后一个下标；D（5）是循环越界后的值。

关联 · 查找失败的返回值（G3）：$-1$ 是"找不到"的标准约定。

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

解析：数组里 $2$ 出现在下标 $0, 2, 4, 6$，共 $4$ 次，cnt 累加到 4。正确答案 B。

实现要点：计数题 = 命中就 cnt++，不 break——与"找下标"题的关键区别。

排除法：A（3）漏数一个；C（5）多数一个；D（8）把数组长度当次数。

关联 · 统计出现次数（O2）：二分版用 upper - lower 求次数。

考点：找第一个匹配的下标（I4）。

解析：从左往右扫，第一个 $2$ 在下标 $1$，命中即 return 0 结束。正确答案 A。

实现要点："第一个"= 按顺序扫、命中即停；如果继续扫不退出，会输出最后一个（$5$）。

排除法：B（3）是第二个 $2$；C（5）是最后一个 $2$；D（2）是值不是下标。

关联 · 第一次出现的位置（K4）：有序数组用二分找第一个。

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

解析：p 记录当前最大下标：$8 > 3 \to p = 1$；$1, 8, 5, 2$ 都不大于 $8$（> 严格），最终 p = 1。正确答案 A。

实现要点：打擂台 = 维护"当前最优位置"p，遇到更优（严格 >）才更新。用严格大于保证有重复最大值时输出第一个。

排除法：B（3）是第二个 $8$ 的位置——>= 才这样；C（8）是值；D（4）是 $5$ 的下标。

关联 · 顺序查找的适用场景（A2）：找最值也是 $O(n)$ 扫描。

考点：哨兵法查找（I6）。

解析：$a[5]$ 放哨兵 $2$，while 一定停：扫过 $3,7,1,9,5$ 都不等于 $2$，最后 i = 5 命中哨兵；i < 5 不成立 → 输出 -1。正确答案 A。

实现要点：哨兵法 = 在数组末尾放目标值，while 循环去掉越界判断 i < n；循环结束用 i < n 区分"真找到"与"撞哨兵"。

排除法：B（5）是哨兵下标，但题目输出的是"找不到"信号；C（2）是目标值；D（0）无依据。

关联 · 查找失败返回 -1（I2）：哨兵法与普通写法殊途同归。

考点：标准二分查找（J1）。

解析：$l=0, r=8$：mid=4 得 $9 < 13 \to l=5$；mid=6 得 $13$ 命中 → ans = 6。正确答案 A。

实现要点：闭区间 while (l <= r) 三件套：a[mid] == x 命中；< x 去右半 l = mid + 1；> x 去左半 r = mid - 1。手算时画区间：每次写下 l, r, mid 三个数。

排除法：B（13）是值不是下标；C（5）是中间过程中的 l；D（7）是下一轮才会查到的位置。

关联 · 闭区间的循环条件（C2）：l <= r 保证最后 1 个元素也被检查。

考点：输出每次的中点（J2）。

解析：l=0, r=8，mid=4 对应 $a[4] = 9$ 直接命中 → 只输出一次 4。正确答案 A。

实现要点：阅读"过程输出"题：把每轮 mid 值排成序列。命中即停，所以输出序列在命中处结束。

排除法：B（4 6 5）是"找不到"时继续收缩的轨迹；C 方向相反；D（9）是值。

关联 · 二分比较次数统计（J3）：同款循环，改数 cnt。

考点：二分比较次数统计（J3）。

解析：$17$ 不存在：mid=4（$10$）→ l=5；mid=7（$16$）→ l=8；mid=8（$18$）→ r=7；l > r 退出，共比较 $3$ 次。正确答案 A。

实现要点：失败时的比较次数 = while 循环体执行的次数；每轮 cnt++ 放循环开头。$n=10$ 时失败比较约 $\lceil \log_2(n+1) \rceil$ 次。

排除法：B（4）多数一轮；C（2）漏数；D（10）是顺序查找最坏次数。

关联 · 二分查找的比较次数（B4）：$n$ 个元素最多约 $\log_2 n + 1$ 次。

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

解析：降序数组左大右小：mid=3 得 $9 > 5 \to l=4$；mid=5 得 $3 < 5 \to r=4$；mid=4 得 $5$ 命中 → 输出 4。正确答案 A。

实现要点：降序二分的收缩方向与升序完全相反：a[mid] < x 时去左半（r = mid - 1），a[mid] > x 时去右半（l = mid + 1）。

排除法：B（5）是升序方向的下标；C（-1）是找不到的信号；D（3）是 $9$ 的下标。

关联 · 降序数组的二分（G2）：方向判断的依据是"哪边更大"。

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

解析：f(0, 6, 11)：mid=3 得 $11$ 命中 → 返回 3。正确答案 A。

实现要点：递归二分 = 三分支：命中返回 mid；太小递归右半 f(mid+1, r, x)；太大递归左半 f(l, mid-1, x)；l > r 是终止（返回 -1）。

排除法：B（11）是值；C（-1）是"找不到"分支的结果；D（4）是 $14$ 的下标。

关联 · 递归与迭代写法（G5）：递归版与 while 版等价。

考点：手写 lower_bound（J6）。

解析：左闭右开 [l, r)：mid=4 得 $5 \geq 5 \to r=4$；mid=2 得 $3 < 5 \to l=3$；mid=3 得 $5 \geq 5 \to r=3$；l == r == 3 输出。正确答案 A。

实现要点：lower_bound 框架 = while (l < r) + 条件 a[mid] < x 时 l = mid + 1，否则 r = mid。r 取"尾后"位置 n（不是 n-1）。返回 l。

排除法：B（4）是第二个 $5$；C（5）是值；D（2）是第一个 $3$。

关联 · 找第一个满足条件的下标（K2）：同一框架的不同题目。

考点：手写 upper_bound（J7）。

解析：与 lower_bound 只差一个等号：mid=4 得 $5 \leq 5 \to l=5$；mid=6 得 $9 > 5 \to r=6$；mid=5 得 $7 > 5 \to r=5$；输出 l = 5。正确答案 A。

实现要点：upper_bound = lower_bound 把条件换成 a[mid] <= x。两者相减 = 出现次数（O2）。

排除法：B（4）是 lower_bound 的结果；C（3）是第一个 $5$；D（6）是 $9$ 的下标。

关联 · 二分统计出现次数（O2）：upper - lower 求次数。

考点：中点溢出的实际输出（K1）。

解析：l + r $= 3.1 \times 10^9 > 2^{31} - 1$：补码截断得 $-1194967296$，除以 $2$ 得 $-597483648$。正确答案 B。

实现要点：int 加法溢出先于除法发生。$3.1 \times 10^9 - 2^{32} = -1194967296$，$/2 = -597483648$。防御：l + (r - l) / 2。

排除法：A（1550000000）是数学正确值，但 int 装不下中间结果；C——C++ 能编译，运行时才溢出；D 无依据。

关联 · 中点写法防溢出（C1）：换写法即免疫。

考点：找第一个满足条件的下标（K2）。

解析：找第一个 $\geq 10$：mid=4 得 $9 < 10 \to l=5$；mid=7 得 $15 \geq 10 \to r=7$；mid=6 得 $13 \to r=6$；mid=5 得 $11 \to r=5$；输出 5。正确答案 A。

实现要点：lower_bound 框架 + 自定义条件 a[mid] < 10。套路：把"满足条件的位置集合"看成单调后缀，找后缀起点。

排除法：B（6）是第二个满足的下标；C（11）是值；D（4）是最后一个不满足的下标。

关联 · 手写 lower_bound（J6）：本题就是 lower_bound 的应用。

考点：上取整中点找最后一个（K3）。

解析：找最后一个 $\leq 10$：mid=4 得 $9 \leq 10 \to l=4$；mid=6 得 $13 > 10 \to r=5$；mid=5 得 $11 > 10 \to r=4$；l == r == 4。正确答案 A。

实现要点：找"最后一个满足"= 可行时 l = mid（不排除 mid）+ 中点向上取整 (l + r + 1) / 2 防死循环。与 K2 的"第一个满足"（向下取整 + r = mid）成镜像。

排除法：B（5）是第一个 $> 10$ 的下标；C（9）是值；D（6）是 $13$ 的下标。

关联 · 死循环：l 与 mid 的关系（H1）：l = mid 必须配上取整中点，本题是正确示范。

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

解析：找第一个 $3$：mid=4 得 $3 \geq 3$ → ans=4, r=3；mid=1 得 $2 < 3 \to l=2$；mid=2 得 $3$ → ans=2, r=1；退出，ans = 2。正确答案 A。

实现要点：a[mid] >= x 时先记录 ans = mid 再向左收缩 r = mid - 1——命中了也别停，继续找更靠左的。

排除法：B（4）是第一次命中的位置（没继续找）；C（3）是中间那个；D（5）是 $5$ 的下标。

关联 · 找第一个等于 x 的位置（C4）：普通二分只保证"命中"，不保证"第一个"。

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

解析：找最后一个 $3$：mid=4 得 $3 \leq 3$ → ans=4, l=5；mid=7 得 $7 > 3 \to r=6$；mid=5 得 $5 > 3 \to r=4$；退出，ans = 4。正确答案 A。

实现要点：与 K4 镜像：a[mid] <= x 时记录并向右收缩 l = mid + 1。两次二分（K4+K5）相减加 1 = 出现次数。

排除法：B（2）是第一个 $3$；C（5）是 $5$ 第一次出现；D（6）是第二个 $5$。

关联 · 找最后一个等于 x 的位置（C5）：概念题 C5 的代码实现。

考点：二分找插入位置（K6）。

解析：找第一个 $\geq 10$ 的下标即插入位置：mid=3 得 $9 < 10 \to l=4$；mid=5 得 $15 \geq 10 \to r=5$；mid=4 得 $12 \geq 10 \to r=4$；输出 4。正确答案 A。

实现要点：插入位置 = lower_bound(x)。注意 r 初始是 n（尾后位置）——插入到末尾时下标恰好是 n。

排除法：B（3）是最后一个 $< 10$ 的下标；C（5）是尾后位置；D（10）是值。

关联 · lower_bound 与 upper_bound（G1）：STL 同名函数返回迭代器。

考点：二分求整数平方根（K7）。

解析：找最大 mid 满足 mid*mid <= 50：$7^2 = 49 \leq 50$，$8^2 = 64 > 50$ → 答案 7。正确答案 A。

实现要点：二分答案套到"整数平方根"：上取整中点 + l = mid；1LL * mid * mid 防 int 溢出（$46341^2$ 就超了）。

排除法：B（8）平方已超 $50$；C（25）是 x/2 的误解；D（6）平方 $36$ 不是最大。

关联 · 二分也能求平方根（G4）：整数版用 l = mid 框架。

考点：砍树二分答案（L1）。

解析：wood(15) = 5 + 0 + 0 + 2 = 7 >= 7 可行；wood(16) = 4 + 0 + 0 + 1 = 5 < 7 不可行 → 最大 $H = 15$。正确答案 A。

实现要点：check(H) 求 $\sum \max(0, h_i - H)$；主循环上取整中点 + wood(mid) >= M 时 l = mid。手算技巧：只验证"答案附近"的 $H = 14, 15, 16$ 即可。

排除法：B（16）木材不够（$5 < 7$）；C（14）可行但不是最大；D（17）木材 $3$ 更不够。

关联 · 砍树问题的单调性（E1）：wood 随 $H$ 单调递减。