CSP-J 学习卷 L22 · 查找与二分

规则：顺序查找平均比较次数是 $(n+1)/2$。

考点：顺序查找的比较次数口径。

解析：目标值等概率出现在任一位置，第 $i$ 个位置要比较 $i$ 次（1 个元素就找到 = 比较 1 次，第 $n$ 个 = 比较 $n$ 次），平均为 $(1+2+\dots+n)/n = (n+1)/2$。

排除法：「约 $n/2$」少了那半次，只有 $(n+1)/2$ 才准确；「约 $n$」是最坏情况不是平均；「约 $\log_2 n$」是二分查找的比较次数，顺序查找最坏要 $n$ 次。

规则：哨兵写法把查找目标放到数组末尾「哨兵位」，让「找不到」的情况也变成「找到哨兵」，循环因此必然命中退出，无需每次检查下标。

考点：顺序查找哨兵写法的正确性。

解析：目标存在时，循环会在它所在位置命中退出；目标不存在时，扫描会一路走到哨兵位 a[n]，那里恰好是 x，也命中退出——总之循环一定在到达真正越界之前退出。所以循环体里只需要判断值是否相等，下标检查被整体省掉。

排除法：哨兵不改变数组有序性，选项内容「数组就变有序了」是错的；越界位置在哨兵位之后、不会被走到，「移出数组之外」说法不成立；「编译器去掉越界检查」既不是哨兵的目的也不可靠。

规则：二分需要「有序」+「可随机访问」两个前提同时成立。

考点：二分的前提条件。

解析：有序保证了「和 a[mid] 比较后能排除一半」；$O(1)$ 随机访问（数组下标）保证每次取 a[mid] 是常数时间。两者缺一不可：无序无法排除一半，链表（只能顺序访问）取 a[mid] 就要 $O(n)$。

排除法：链表有序也做不了 $O(\log n)$ 二分，选项内容「无论什么结构」是陷阱；有序性不能省，「不必有序」直接破坏正确性；元素重复只影响返回哪个位置，不影响能否二分，「互不相同」不是前提。

规则：只有数组有序，「a[mid] 大 → 目标在左半边」这个排除才是可靠的；无序时两边都可能含有目标，砍掉一边就可能丢掉答案。

考点：二分必须有序的根本原因。

解析：二分的每一步都在做「既然 a[mid] 和 x 的大小关系已知，那么含 x 的区域只可能在一边」。这个论断依赖整段有序：若 a[mid] > x，只有「左边所有元素都 $\le x$」才能推出目标在左半边——无序数组不保证这一点。所以无序时比较 a[mid] 什么都排除不了。

排除法：「稍慢但正确」与「更快」都建立在还能排除的基础上，实际是结果错误；越界是无稽之谈，mid 始终在区间内。

规则：复杂度说的是「规模变大时的增长趋势」，小规模下常数因子往往更关键，顺序查找更简单更快。

考点：复杂度分析的应用边界。

解析：二分比较次数约 $\log_2 10 \approx 4$ 次，顺序查找平均约 $5.5$ 次，差距极小；但二分每轮要做两次比较、算 mid、多次分支，常数更大。对 $n=10$ 只查一次，简单直接的顺序查找通常更快，也更不容易写错。复杂度优势在 $n$ 很大时才体现。

排除法：题目说数组有序，「顺序查找不要求有序」答非所问；二分在小数组不会越界（区间端点始终受控）；二分在任意 $n$ 上都是 $O(\log n)$，不会退化为 $O(n^2)$。

规则：二分最多比较次数是 $\lceil \log_2 n \rceil$（$n=100$ 时为 $7$）。

考点：比较次数上界公式。

解析：每次比较最多把区间一分为二。$k$ 次比较最多能区分 $2^k$ 个位置，要覆盖 $n$ 个位置需要 $2^k \ge n$，即 $k \ge \log_2 n$，取整得到 $\lceil \log_2 n \rceil$。$2^6 = 64$ 不够覆盖 100 个位置，所以必须 7 次。注意「$\log_2 100 \approx 6.64$」本身没错，但取的是向上取整不是四舍五入，得到 7。

排除法：「四舍五入 6.64 得 7」数值碰巧对了，但理由错误——$\log_2 99 \approx 6.63$ 也四舍五入到 7，可 $\lceil \log_2 99 \rceil = 7$ 的根据是向上取整；「排除 2 个元素」是把顺序查找的排除量安到二分头上；「等于数组长度」是顺序查找的最坏情况。

规则：$\lceil \log_2 n \rceil$ 在 $n = 1000$ 时为 $10$，在 $n = 10^6$ 时为 $20$。

考点：手算比较次数表。

解析：$2^{10} = 1024 \ge 1000$，所以 $\lceil \log_2 1000 \rceil = 10$；$2^{20} = 1048576 \ge 10^6$，所以 $\lceil \log_2 10^6 \rceil = 20$。二分查找 100 万个数也只要 20 次比较——这是它强大的直观体现。

排除法：$2^9 = 512 < 1000$、$2^{10} = 1024 \ge 1000$，所以 $n=1000$ 是 10 不是 11 也不是 9；「等于数组长度」把顺序查找的最坏情况安到了二分头上。

规则：二分的标志是「一次比较后确定性排除约一半」，猜数游戏（大了/小了）正是它的日常原型。

考点：二分思想的本质。

解析：猜数时对方回答「大了」就能排除右半边，回答「小了」排除左半边，每轮区间减半，$\lceil \log_2 N \rceil$ 次内必中——这与二分查找、二分答案同构。

排除法：「逐核对」是顺序查找；「拆 10 份同时找」是并行不是二分；「随机碰运气」无法保证每次都排除一半，最坏可能一直不中。

规则：找第一个匹配位置和判断存在性都可以「见 x 就停」；只有统计个数必须扫完整个数组。

考点：顺序查找的三种变体口径。

解析：找第一个：循环里 a[i] == x 就 return i，第一个命中的必然最先被遇到；判存在：命中就 break 并标记 found，同样不用扫完；统计个数：后面的元素还可能有匹配，必须 i 走到底才能给总数。三个版本的中途退出行为不同，返回值口径也不同。

排除法：「都必须扫完」只对统计个数成立；「找第一个和判存在都要扫完」错在忽略了命中即可停；「中途退出复杂度不是 $O(n)$」是把最坏 $O(n)$ 理解成了必须跑满 $n$ 步。

规则：最坏 = 目标在最后一个位置（$n$ 次）；平均 = $(n+1)/2 = 5$ 次。

考点：顺序查找的次数计算。

解析：最坏情况目标在 a[8]，要比较完 9 个元素才找到，$9$ 次。平均情况目标等概率落在任一位置，比较次数 $1+2+\dots+9$ 的平均是 $(9+1)/2 = 5$ 次。

排除法：最坏是 9 不是 10（不用比较越界哨兵位）也不是 8；平均是 5 不是 9 或 4。

规则：单次查找 + 无序数据 = 顺序查找更优（$O(n)$ vs 排序 $O(n \log n)$）。

考点：顺序查找 vs 排序后二分的复杂度权衡。

解析：若只查一次，排序 $O(n \log n)$ + 二分 $O(\log n)$ ≈ $O(n \log n)$，比直接顺序查找 $O(n)$ 还慢；而且排序可能破坏原数组顺序。只有「查很多次」（$m \gg \log n$ 次）时，先排序再二分才划算。这正是「什么时候顺序查找反而合适」的答案。

排除法：「更准确」无关，两者都能查存在性；「排序丢数据」排序是重排不是丢；「无序会死循环」二分前提不满足时结果未定义，但通常不是死循环，是错误结果。

规则：$\lceil \log_2 100 \rceil = 7$——每次回答最多排除一半，7 次足够区分 $2^7 = 128 > 100$ 种可能。

考点：猜数游戏与二分比较次数的对应。

解析：每次「大了/小了」的回答都让候选区间减半。$k$ 次回答最多区分 $2^k$ 个数，$2^6 = 64 < 100$ 不够，$2^7 = 128 \ge 100$ 够，所以最多 7 次。这与二分查找的最大比较次数公式完全一致。

排除法：$6$ 次只能区分 64 个数不够覆盖 100；$100$ 次是顺序猜；$50$ 次没有依据。

规则：闭区间写法每轮都通过 l = mid + 1 或 r = mid - 1 把 mid 排除出区间，区间至少缩小 1，因此必然结束。

考点：循环能终止的根本保证 = 区间严格收缩。

解析：不管 a[mid] 和 x 是什么关系，三个分支都处理了：相等就返回；a[mid] < x 时目标只可能在右边，l 变成 mid + 1；a[mid] > x 时 r 变成 mid - 1。无论哪条路，mid 都被排除，[l, r] 长度严格减小，不会原地踏步。

易错：有些同学把「不死循环」寄托在 return mid 上，其实把命中分支删掉、改成继续收缩，循环照样能结束（只是丢了答案）——终止性来自区间收缩，不来自 return。

排除法：「编译器优化」在 C++ 里没有这回事；「靠 return 退出」把退出条件和终止性混为一谈；「mid 等于 l 区间不变」恰恰说反——l = mid + 1 保证即使 mid == l，新区间也从 l+1 开始，一样缩小。

规则：死循环的病根是收缩时没有把 mid 排除出区间——r = mid 在 mid == r 时让 r 保持原值，区间不再缩小。

考点：死循环的唯一病根 = 收缩不排 mid；两元素极端情况自查法。

解析：手动模拟 a = {1,3,5,7,9}、x = 2：初始 l=0, r=4。第 1 轮 mid=2，a[2]=5 > 2，r = mid = 2；第 2 轮 mid=1，a[1]=3 > 2，r = mid = 1；第 3 轮 l=0, r=1，mid=0，a[0]=1 < 2，l=1。此时 l=1, r=1，mid = 1，a[1]=3 > 2，执行 r = mid = 1——r 不变！下一轮 l=1, r=1 又是同样的 mid=1，无限循环。问题就出在区间缩到 2 个元素后，r = mid 让 r 钉死在 mid 上。

排除法：「数据选得不好」——数据没问题，任何 l == r 且 a[l] > x 的局面都会触发死循环；「越界」——mid 始终落在 [l, r] 内，不会越界；「只是变慢」——这不是效率问题，程序直接卡死，永远给不出答案。

规则：两元素自查法——模拟只剩 2 个元素时若出现「l = mid 或 r = mid 使指针钉住」，必死循环。

考点：死循环两元素自查法。

解析：a = {2,4,6,8}、x = 3：第 1 轮 l=0, r=3, mid=1，a[1]=4 > 3，误写代码执行 r = mid = 1。第 2 轮 l=0, r=1, mid=0，a[0]=2 < 3，l = mid + 1 = 1。此时 l=1, r=1——注意区间是直接「从两个元素跳到只剩一个」，没有经历 l=1, r=2。再看题目给的起点 l=1, r=2：mid = 1 + (2-1)/2 = 1，a[1]=4 > 3，r = mid = 1，区间变 l=1, r=1；下一轮 mid = 1 还是它自己，a[1]=4 > 3 恒成立，r = mid = 1 永远不动，死循环。

排除法：「r = mid - 1 = 0」是正确写法会做的事，误写版本没有减一；「l = mid + 1」只有在 a[mid] < x 才走，这里 4 > 3 走的是 else；「mid = 2」错在 mid = l + (r - l) / 2 = 1 + 0 = 1，不会取到 2。

规则：循环不变量「a[l-1] < x 且 a[r+1] > x」在结束时合并成 l = r+1，得到 a[l-1] < x 且 a[l] > x——l 正是第一个大于 x 的位置。

考点：闭区间写法的结束状态。

解析：看代码的分支：a[mid] < x 时 l = mid + 1，这保证新 l 之前的所有元素（含 a[mid]）都小于 x，即 a[l-1] < x；a[mid] > x 时 r = mid - 1，这保证新 r 之后的所有元素都大于 x，即 a[r+1] > x。两个性质在每轮循环里都保持（循环不变量）。结束时 l = r + 1，代入得 a[l-1] < x 且 a[l] > x，所以第一个大于 x 的元素下标就是 l。

排除法：「l 一直增大停在末尾」只对全小于 x 的情形成立，不是一般规律；「r 是第一个大于 x 的位置」方向反了，r 是最后一个小于 x 的位置；「l 一定等于数组长度」同样是只有全小于时才成立。

规则：终止性来自区间收缩（不来自 return），但答案会被排除出区间而丢失——删掉 return 且改成继续收缩，结果是正常结束却返回 -1。

考点：命中分支的作用是「记录答案并退出」，而不是「保证终止」。

解析：模拟 a = {3,5,7}、x = 5：l=0, r=2, mid=1，a[1]=5 == x，但代码不返回，执行 l = mid + 1 = 2；继续 l=2, r=2, mid=2，a[2]=7 > 5，r = mid - 1 = 1；l=2, r=1 退出循环，返回 -1。循环没有死（每轮都收缩），但 5 所在的下标 1 已经被排除，答案回不来了。

排除法：「命中后不再更新任何指针」是另一种错误改法（什么都不做）才会死循环，本情境是继续收缩，不会死；「返回值不受影响」显然错——返回的是 -1；「返回错误下标」它根本没返回下标，返回的是 -1。

规则：分支写反 = 排除方向写反，每次都在排除「可能含答案」的那一半，最后区间交叉返回 -1。

考点：比较方向与收缩方向的配套关系。

解析：a = {2,4,6,8}、x = 6：l=0, r=3, mid=1，a[1]=4 < 6，误写代码走 a[mid] < x 分支执行 r = mid - 1 = 0；l=0, r=0，mid=0，a[0]=2 < 6，r = mid - 1 = -1；l=0, r=-1 退出，返回 -1。看：正确的 x=6 明明存在，却在第一轮就被排除——因为 4 < 6 本该往右找，误写版本却把右半砍掉。

排除法：「死循环」不会发生，l、r 每次都在变，很快交叉；「偶尔找到」不对——方向恒定错误，每次都丢答案；「仍然正确」忽略了两分支走反的事实。

规则：已比较过的 mid 必须排除出新区间，所以左边界推进一格。

考点：闭区间写法两分支的配套收缩。

解析：a[mid] < x 说明 a[mid] 不可能是答案（它太小），而比它还小的左边元素更不可能，所以整个左半边都排除，l 越过 mid 到 mid + 1。这与 else r = mid - 1 对称：两个分支都把 mid 排除出区间，这正是「不死循环」的保证。

排除法：填 mid 会把 a[mid] 留回区间，下一轮重复比较它（虽不会立即死循环，但多一轮且破坏不变量）；填 mid - 1 更糟，又把左半边元素含回区间；填 mid + 2 跳过了 mid + 1，可能漏掉答案。

规则：查不到时结束状态恒为 l == r + 1，且 l 是第一个大于 x 的插入位置。

考点：闭区间写法的结束状态。

解析：模拟 a = {2,4,6,8,10}、x = 7：l=0, r=4, mid=2，a[2]=6 < 7，l=3；l=3, r=4, mid=3，a[3]=8 > 7，r=2；l=3, r=2 退出循环。此时 a[2]=6 < 7 且 a[3]=8 > 7，7 插入在 6 和 8 之间，位置正好是 l = 3。

排除法：「l 是最后一个小于 7 的下标」那个是 r=2，不是 l；「l=4, r=3」数值错——l 到 3 就停了；「l=2」错，6 的位置是 2，而插入位置在其后一位。

规则：递归版与迭代版是同一算法的两种表达——「出口 = 循环条件失败」「每层递归 = 循环一轮」，规模每层至少减半，复杂度同为 $O(\log n)$。

考点：递归二分与迭代二分的等价性。

解析：对照看：迭代版的 while (l <= r) 条件失败（l > r）对应递归版的 if (l > r) return -1 出口；迭代版一轮里做的「算 mid、比较、缩一半」正是递归版一层调用做的事，且下一层区间 [mid+1, r] 或 [l, mid-1] 与迭代版的 l = mid + 1 或 r = mid - 1 完全一致。所以比较次数相同，递归版只多一次函数调用的常数开销。递归版的「死循环」长这样：如果收缩写错导致区间不缩小，会无限递归，最终栈溢出——和迭代版死循环是同一种病。

排除法：「慢一个数量级」不对，同是 $O(\log n)$ 只差常数；「递归版不会终止」只在写错时成立，正确写法照样 $O(\log n)$ 层就结束；「只能查精确值」递归同样能写边界查找，只是传参形式不同。

规则：递归二分的出口是循环条件失败（区间空），深度 $O(\log n)$。

考点：递归二分的终止条件与栈深。

解析：每次递归调用都把当前区间切成两半，只往含目标的那一半走，所以调用链长度最多 $\lceil \log_2 n \rceil$ 层。每层占用一个栈帧，栈深 $O(\log n)$。出口 l > r 表示区间为空、目标不存在，返回 -1 逐层回溯。

排除法：「找不到就永远递归」忽略了 l > r 出口——任何查找最终都会把区间缩空；「深度 $O(n)$」错，每层减半，深度是对数；「系统自动处理」没有这回事，出口必须自己写。

规则：ans 初值 = 「不存在」的统一口径，必须落在合法下标范围之外，取 n 正好。

考点：ans 记录版的哨兵初值设计。

解析：合法下标是 $0 \sim n-1$。只有当某次 a[mid] >= x 时 ans 才被更新成真实下标；如果整个数组都小于 x，ans 一直保持初值。这个初值不能是合法下标，否则调用方会把一个从未命中的位置当答案。取 n 后，调用方判断 ans == n 即「不存在」。

排除法：「下标就是 n」错，数组下标最大是 n-1，n 恰好越界；「效果一样」错——全小于 x 时取 0 会返回假答案 a[0]；「整型上限」没必要，n 就够了。

规则：红蓝染色是二分的循环不变量表述：两种颜色的分界线就是答案位置，二分是在反复逼近这条分界线。

考点：二分的循环不变量视角。

解析：不管当前区间多大，循环始终保证：l 之前的元素都满足某性质（蓝色），r 之后都违背（红色），中间的 [l, r] 是「未知区」。每次取 mid 判断颜色，就能把未知区砍掉一半，直到 l 与 r 相邻，l 和 r 分别是最后一个蓝色和第一个红色，答案就是这条分界线。这与普通二分「找第一个满足性质的位置」完全同构，只是换了一套说法。

排除法：「完全不同算法」错，就是二分的另一套表述；「物理重排」多此一举，颜色是逻辑概念；「只适用实数」错，整数二分照样能用。

规则：按位看，(l & r) 是两数相同的位，(l ^ r) >> 1 是不同位之和的一半，相加正好是 $(l + r) / 2$ 向下取整。

考点：位运算求平均数的原理。

解析：任意两个二进制数相加 l + r，可以拆成「同位相加无进位的结果」加上「进位」。l ^ r 给出哪些位不同（这些位相加不会进位），l & r 给出哪些位相同（这些位相加会进位 1 到高一位）。因此 (l & r) + ((l ^ r) >> 1) = 进位项 + 不同位的一半 = (l + r) / 2 向下取整。它与更常用的 l + (r - l) / 2 数学等价，只是换成了位运算的形式，面试里偶尔见到，正常写法用 l + (r - l) / 2 即可。

排除法：不是两倍平均数，方向反了；不是绝对值也不是最大公约数，那些运算与按位拆无关。

规则：ans 记录版照常收敛——6 不存在但第一个大于等于 6 的位置是 3，返回 3。

考点：ans 记录版与左边界的一致性。

解析：l=0, r=4, mid=2：a[2]=5 >= 6 假，l=3；l=3, r=4, mid=3：a[3]=7 >= 6 真，ans=3, r=2；l=3, r=2 退出，返回 3。7 是第一个不小于 6 的元素。注意 ans 初值 n 只在「全数组都小于 x」时保留，这里命中过，ans 被更新为 3。

排除法：4 是初值口径，本数据命中了真实下标；2 是 5 的位置，5 < 6 不满足；本写法不用 -1 表示不存在。

规则：x = 7 落在 6 和 8 之间，二分只走了 2 轮区间就空了。

考点：闭区间写法的追踪与比较次数。

解析：第 1 轮 l=0, r=4, mid=2，a[2]=6 < 7，l=3；第 2 轮 l=3, r=4, mid=3，a[3]=8 > 7，r=2；l=3, r=2 退出。循环体执行 2 次，比较了 6 和 8 两个位置。这正是闭区间写法查不到的典型过程：l 和 r 夹向插入点两侧然后交叉。

排除法：3 次是 a = {2,4,6,8,10} 找其他值时的可能轮数，这里只走 2 轮；4、5 次更多。

规则：n = 5 时第一次 mid = 2 恰好命中 a[2] = 5，只递归 1 层。

考点：递归二分的层数与返回值。

解析：l=0, r=4, mid = 0 + (4-0)/2 = 2，a[2] = 5 == x，直接返回 2，没有进入更深的递归。findX 只被调用了 1 层。若查不存在的值，层数约等于 $\lceil \log_2 n \rceil$。

排除法：mid 第一次就中，递归不是 3 层；返回的是下标 2 不是值 3；递归 2 层也不对。

规则：左边界统一为「第一个 $\ge x$」，右边界统一为「第一个 $> x$ 的前一位」=「最后一个 $\le x$」。

考点：左右边界的标准定义。

解析：左边界 lower_bound(x) 返回第一个不小于 x 的位置；右边界则借「第一个大于 x 的位置减 1」得到最后一个不大于 x 的位置。这两者都不要求 x 一定存在——比如找 x 的插入位置时用的就是左边界。

排除法：「最后一个小于 x」那是左边界的前一个位置；「不存在就返回 -1」与边界版的设计相反，边界版用返回 n 表示越界；「只在有重复时不同」不对，左边界右边界定义本身不同，与重复无关。

规则：只要 mid 可能是答案就不能排除它——a[mid] >= x 时 mid 就是候选，必须 r = mid 保留。

考点：边界写法中「可能成为答案的元素不能删」。

解析：a[mid] >= x 说明 mid 已经满足「不小于 x」，它可能是第一个（前面也许还有更小的合法下标，需要继续往左找），也可能是唯一的一个。写成 r = mid 把 mid 留在新区间 [l, mid] 继续左压，最终 l == r 收敛到第一个满足者。若写 r = mid - 1，就把 mid 这个候选排除掉——若 mid 恰是唯一的第一个，答案就丢了。

排除法：「排除更多更高效」——多排一个 mid 不是效率问题，是正确性问题；「无法退出循环」不会，r = mid 配合 l < r 与 mid 下取整保证 mid < r，区间照常收缩；「完全等价」恰恰是本题要纠正的误区。

规则：l = mid 会保留 mid，因此必须上取整保证 mid > l；否则相邻两数时 mid == l，区间不收缩。

考点：取整方向与收缩方式的配套。

解析：lo = 3, hi = 4 时，下取整 mid = 3 + (4-3)/2 = 3。若 check(3) 为真，lo = mid = 3，lo、hi 仍是 3、4——死循环。正确写法是 mid = lo + (hi - lo + 1) / 2（上取整），相邻时 mid = 4，check(4) 为真则 lo = 4 区间变空，为假则 hi = 3 同样收缩。口诀：l = mid 配 mid + 1 的取整，让 mid 严格大于 l。

排除法：「四舍五入更平均」没有这回事，取整方向由收缩方式决定；「取整方向不影响正确性」恰好相反，选错方向就是死循环；「mid < lo」不可能，mid 恒在 [lo, hi] 内，问题是 mid == lo 而不是越界。

规则：r = mid 会保留 mid，因此必须下取整保证 mid < r；否则相邻两数时 mid == r，区间不收缩。

考点：取整方向的对称配套（与上题的镜像）。

解析：lo = 3, hi = 4 时，上取整 mid = 3 + (4-3+1)/2 = 4。若 check(4) 为真，hi = mid = 4，lo、hi 仍是 3、4——死循环。正确写法是 mid = lo + (hi - lo) / 2（下取整），相邻时 mid = 3，无论 check(3) 真假区间都收缩。规律很对称：l = mid 上取整，r = mid 下取整——哪个端点被保留，就让 mid 别落在那个端点上。

排除法：「上取整不是可行值」与 check 的真假无关，问题在区间不收缩；「奇数位置不稳定」无稽之谈；「两种取整都死循环」错，配对的取整方向是安全的。

规则：l < r 是循环唯一条件，停止时 l == r；配合「答案始终在区间内」的不变量，这个共同位置就是答案。

考点：边界写法的结束状态。

解析：循环变量 l、r 是整数，while (l < r) 只可能因 l == r 退出（不会出现 l > r——l = mid + 1 在 mid 下取整时最多让 l 达到 r，r = mid 最多让 r 回到 l）。再看不变量：a[mid] >= x 时答案若存在必在 [l, mid]，r = mid 保留；否则答案必在 [mid+1, r]，l = mid + 1。每轮都保留了答案所在区间，所以收敛点必然就是第一个 >= x 的位置。

排除法：「l > r」是闭区间写法的结束状态，边界写法不可能越过；「还要再判断 a[l]」边界写法不要求 x 存在，返回的 l 直接就是答案（可能为 n 表示越界）；「相差 1」不可能，整数下 l < r 为真的最小差距是 1，缩到 0 就退出。

规则：统一口径——所有边界都表达为「第一个大于等于/大于 x 的位置」，右边界只是「第一个大于 x 再减一」。

考点：右边界与半开区间的统一性。

解析：若直接写「最后一个 <= x」，循环里要维护的是 l = mid（保留候选）+ 上取整，与左边界模板方向正好相反，两套模板容易背混。而「第一个 > x 减一」用的还是同一套「第一个…」模板，只是比较符号从 >= 换成 >，返回前减一即可。例：a = {1,3,3,3,5,5,8}，第一个大于 3 是下标 4，减一得 3，正是最后一个 3。

排除法：「会死循环」「会越界」都无依据，直接写也能正确实现，只是要多维护一套相反方向的模板；「不减会差一位」减一是逻辑需要（最后 <=x = 第一个 >x 前一位），不是下标从 0 起的修正。

规则：边界写法的答案域是 $[0, n]$，n 专门留给「全部不满足」的情形；拿到 n 必须先判「不存在」再访问。

考点：返回 n 的含义与越界防护。

解析：数组下标是 $0 \sim n-1$，而 lowerB 的答案域包含 n（半开区间 [l, r) 的 r 初值就是 n）。全数组都小于 x 时没有任何合法位置满足，函数返回 n 作为「不存在」的记号。此时直接访问 a[n] 就越界。正确的用法是 int idx = lowerB(...); if (idx < n) { ... } else { /* 不存在 */ }。

排除法：「4 是最后一个元素下标」最后一个下标是 3，4 恰好越界一位；「比较时已经越界」比较发生在 mid 上，mid 恒在 [0, n-1]，不会越界；「返回 -1」那是闭区间写法的口径，边界写法用 n。

规则：悬空端点保证 mid 永远取不到 l 或 r，于是 l = mid 和 r = mid 两条路都严格收缩——取整方向自然无所谓。

考点：开区间悬空写法免疫死循环的原理。

解析：l 初始为 -1、r 初始为 n，它们不是合法下标、不会被访问（a[mid] 里 mid 严格在 (l, r) 内，即 $0 \sim n-1$）。循环里无论 mid 怎么取整，它都在 l 和 r 之间，所以 l = mid 使 l 至少增 1（mid > l），r = mid 使 r 至少减 1（mid < r）。区间长度 r - l - 1 每轮至少减 1，必然收敛。

排除法：「靠 return 退出」这个函数没有 return mid，靠的是循环条件 l + 1 < r 自然失效；「特殊公式」没有，就是普通下取整；「l 是答案」终止时返回 r，l 是最后一个不满足的位置。

规则：开区间写法逐轮把 l 或 r 拉向答案，终止时 l + 1 == r，返回 r。

解析：a = {2,4,6,8}，x = 5。第 1 轮 mid = -1 + (4-(-1))/2 = 1，a[1] = 4 >= 5 为假，l = mid = 1；第 2 轮 mid = 1 + (4-1)/2 = 2，a[2] = 6 >= 5 为真，r = mid = 2；此时 l + 1 = 2 == r，循环结束，返回 r = 2。第一个大于等于 5 的元素是 a[2] = 6，正确。

排除法：「(-1,4) → (0,4)」错在 mid 从 0 开始——mid = -1 + (4-(-1))/2 = 1，第一轮就跳到 1，l 直接变 1 不会经过 0；「返回 3」错，终止时 r = 2。

规则：出现次数 = upperB(x) - lowerB(x)，等于「最后一个小于等于减一」的反向。

考点：出现次数的 lb/ub 计数法。

解析：a = {1,2,2,2,3,4,4,5}。x = 2：lowerB 返回 1（第一个 2），upperB 返回 4（第一个 > 2 是 3 的位置），4 - 1 = 3 个 2。x = 4：lowerB 返回 5，upperB 返回 7（第一个 > 4 是 5 的位置），7 - 5 = 2 个 4。

排除法：x=2 是 3 不是 2 或 1；x=4 是 2 不是 1 或 3。

规则：边界情形——ub - lb 在元素全等时给出全长，在元素不存在时给出 0，两种极端都自动正确处理。

考点：出现次数计数的边界行为。

解析：a = {1,1,1,1}。x = 1：lowerB(1) = 0（第一个 >= 1 是下标 0），upperB(1) = 4（第一个 > 1 不存在，返回 n = 4），4 - 0 = 4 个。x = 0：lowerB(0) = 0，upperB(0) = 0（第一个 > 0 是下标 0），0 - 0 = 0 个。两个极端值都对。

排除法：x=1 是 4 不是 3 或 1；x=0 是 0 不是 4 或 1。

规则：排序后 lower_bound 直接定位元素位置或插入位置。

考点：排序与边界查找的配合。

解析：排序后 a = {2,2,5,8,9}。lower_bound(5)：第一个 >= 5 是下标 2（a[2] = 5），返回 2。lower_bound(7)：第一个 >= 7 是 8 的下标 3，返回 3——这就是 7 的插入位置。

排除法：5 前面有两个 2，位置是 2 不是 1；7 插在 5 和 8 之间，位置 3 不是 4。

规则：x 比所有元素都小时，第一个大于等于它的就是 a[0]，返回 0。

考点：左边界的下界情形。

解析：a[0] = 5 >= 3，第一个满足的就是下标 0。二分会一路把 r 往左压：l=0, r=4, mid=2，a[2]=7 >= 3 真，r=2；mid=1，a[1]=6 >= 3 真，r=1；mid=0，a[0]=5 >= 3 真，r=0；l=0, r=0 退出，返回 0。

排除法：1、4、-1 都是错误方向；-1 是闭区间写法的不存在口径，本模板用 0 表示「最小位置满足」。

规则：无重复数组上，右边界 <= x 就是 x 本身的位置。

考点：右边界与精确位置在无重复时的重合。

解析：第一个大于 5 的元素是 7，下标 3，减一得 2，即 5 的位置。无重复时「最后一个 <= 5」只有 5 自己，所以右边界恰好就是精确查找的答案。有重复时两者才分离（右边界 = 最后一个相等元素）。

排除法：3 是第一个大于 5 的位置（减一前的结果）；1 是 3 的位置；0 是 1 的位置。

规则：l + (r - l) / 2 与 (l + r) / 2 数学等价，但后者在 l + r 溢出时出错，前者用差值规避溢出。

考点：防溢出的 mid 写法。

解析：int 上限约 $2.1 \times 10^9$。若 l = r = 1.5 \times 10^9，l + r = 3 \times 10^9 超过上限，结果溢出（常见是变成负数），mid 变成负下标直接越界。而 r - l 最大也不超过整个数组长度（比如 2 \times 10^9 以内），l + (r - l) / 2 每步都在合法范围内。(l + r) / 2 在竞赛中数据不大时没问题，但 l + (r - l) / 2 是写不坏的稳妥形式。

排除法：「完全等价永远一样」忽略了溢出——数学等价但机器实现会溢出；「加法比减法快」编译后基本无差别，不是设计理由；「l 很小时算负数」不可能，l + (r-l)/2 恒在 [l, r] 之间。

规则：l = mid 配下取整，在区间只剩两个元素且 l 被保留时，l 钉住不动——自查法立刻暴露。

考点：死循环两元素自查法。

解析：取 a = {2, 4, 6}、x = 8（一直走 a[mid] < x 分支）。第 1 轮 l=0, r=2, mid=1，a[1]=4 < 8，l = mid = 1；第 2 轮 l=1, r=2, mid=1，a[1]=4 < 8，l = mid = 1——区间一直是 [1, 2]。问题精确出现在「只剩两个元素」时：mid 下取整等于 l，l = mid 不产生任何变化。正确写法是 l = mid + 1（mid 已比较过，排除）。

排除法：「a[1] > x 死循环」——a[1] > x 走 r = mid - 1 = 0，区间变空结束，不会死；「l=2, r=3」这个数据下区间只会到 [1,2]；「第一轮就不收缩」第一轮正常收缩，问题在第 2 轮才开始。

规则：机器精度有限，double 大约 16 位有效数字；eps 取得比机器精度还小时，差值会「停住」不再缩小，while (r - l > eps) 永不满足退出条件。

考点：实数二分的 eps 陷阱。

解析：假设区间 [a, b] 已经缩到 $[1.4142135623, 1.4142135624]$ 这种相邻双精度值，两个数中间没有别的 double 可表示，mid = (l + r) / 2 会等于 l 或 r，r - l 停在约 $10^{-16}$，不再变化。若 eps = 1e-15，循环条件 r - l > 1e-15 恒为真，死循环。解决：用固定迭代次数（如 100 次）或把 eps 放宽到 1e-7 左右（满足题目精度即可）。

排除法：「只是慢」——不是慢，是永远不结束；「r - l 变负」不可能，r 始终不小于 l；「sqrt 有误差」与判断逻辑无关。

规则：二分答案的前提是「可行性关于候选值单调」；切割成本版的最优解依赖切割顺序，可行性不单调，二分给的是安静的错误答案（不会报错）。

考点：单调性缺失时二分的失效方式。

解析：二分答案能工作的本质是：候选值 x 的可行性是「假…假 真…真」的阶梯形。切割成本版的费用取决于切割顺序（先切中间大块费用高、先切两端小块费用省），同样的目标段长集合，按不同顺序总费用不同——「费用不超过某值」不构成单调阶梯。于是二分夹出的位置可能落在非单调区间的中间，返回一个错误值，程序不崩溃也不死循环，安静地错。反例直觉：与「等长切段」版（每段长度确定、可不可行单调）对比，那才是二分适用的模型。

排除法：「整数无效」错，二分答案大量处理整数（跳石头、切蛋糕）；「钢条太短」与算法正确性无关；「必须动态规划」不是不能用二分的理由，关键是单调性，而非算法类别。

规则：初始上界必须盖住答案；不盖住时二分会把答案「夹」到 hi 上，返回一个偏小的错误值。

考点：答案域选取，上界常取「最大可能 + 1」。

解析：二分答案的区间不变量是「答案在 [lo, hi] 内」。若真答案 6 大于 hi = 5，则区间里根本没有答案。最大可行值二分会发现 check(5) 为真（可行）就保留 5 并向上收缩，可 hi 已经是上界，最终 lo = hi = 5，返回 5——一个「最大可行」但小于真答案的值。所以工程上常把上界取成「最大可能 + 1」（如所有蛋糕长度和 + 1），宁可多一个不可行的顶格值，保证真答案在区间内。

排除法：「越界报错」二分下标不会越界，答案只是错；「死循环」正常收缩不会死；「自动扩展」代码不会自我修正。

规则：check 的语义（多大可行）必须和收缩方向（l = mid 还是 r = mid）配套，否则收敛到另一侧的边界值。

考点：最大可行 / 最小可行的收缩方向。

解析：砍树中 h 越高可得木材越少，check 是「小真大假」（低高度可行、高高度不可行），所以求最大可行用 check(mid) 为真时 lo = mid（往大方向保留）。若误按「大真小假」的最小可行逻辑写（真时 hi = mid），收敛结果会偏小，得到的是「最矮的可行高度」附近的错误值。注意它不会死循环——收缩仍进行，只是答案错方向。判断方向的口诀：看 check 为真时答案应该往哪边更大/更小，然后决定保留哪一端。

排除法：「只是慢」错，答案错；「死循环」两分支都收缩不会死；「越界」无关。

规则：写法迁移必须整体换「区间口径 + 收缩 + 结束判定」，只动一行必然破坏一致性。

考点：写法族之间的等价迁移。

解析：三个要素耦合在一起：① 区间定义（闭区间 [l, r] 还是半开 [l, r)，决定 r 初值是 n-1 还是 n）；② mid 处置（能不能排除 mid——闭区间两分支都排除，边界写法保留候选那侧不排除）；③ 结束状态（l > r 返回 -1 vs l == r 直接当答案）。只把 while (l <= r) 改成 while (l < r) 而保留 r = mid - 1：当答案是 r 端点时会被 mid 取到吗？可能因 r 被 mid - 1 排除而丢解，或在相邻时死循环。所以等价迁移要么整套替换，要么用教材里现成的等价模板。

排除法：「只改循环条件」是本题纠正的误区，必出问题；「循环条件本来就一样」两种模板一个 <= 一个 <；「加 return -1 才能编译」纯属虚构，编译与写不写 return 无关。

规则：降序数组的比较方向全部镜像：a[mid] > x 时目标在左、a[mid] < x 时目标在右，分支、收缩、边界三者配套翻转。

考点：降序数组的二分。

解析：升序时 a[mid] < x 说明目标在右半边（l = mid + 1）；降序时 a[mid] < x 说明 a[mid] 右边更小，目标在左半边（r = mid - 1）。即 l = mid + 1 与 r = mid - 1 的角色对调，同时查边界时比较符号也反转（找第一个 <= x 之类）。若只改一处，比如只把分支条件对调而收缩方向照旧，就会两分支同时排除错误半区，答案丢失。这与 C++ 的 greater<int>() 比较器对应：把 a[mid] > x 的判定整体按 > 与 < 互换。

排除法：「直接能用」错，前提变了；「只换比较符号」漏了收缩方向也要反；「无法二分只能排序」错——降序只需镜像写，不必排序（排序反而破坏降序结构或增加开销）。

规则：二分依赖 $O(1)$ 随机访问取 mid；链表只能顺序访问，每轮找中间元素都要 $O(n)$ 时间。

考点：二分的数据结构前提。

解析：数组用 a[mid] 一步取到中间元素；链表要取第 mid 个节点必须从头遍历 mid 步。一轮 O(n)，共 $\log_2 n$ 轮，总 $O(n \log n)$——还不如直接顺序扫描（$O(n)$）。所以对链表找元素就用顺序扫描，或用跳表/平衡树这类支持快速跳转的结构。

排除法：「不能存放整数」链表当然能放任意类型；「链表没法排序」链式归并排序是常见算法，能排序；「死循环」与数据结构无关的臆测。

规则：旋转数组折半后必有一半有序，判断哪半有序后根据「最小值在无序半」决定排除哪边，$O(\log n)$ 收敛到最小值。

考点：旋转数组的二分。

解析：对 {4,5,6,7,0,1,2}：l=0, r=6, mid=3，a[mid]=7。左半 {4,5,6,7} 是递增的（a[l] <= a[mid]），说明最小值不在左半有序段，在右半 [mid+1, r]；反之若右半有序，最小值在左半。每次排除一半，最后 l 停在最小值处。注意有重复元素时 a[l] == a[mid] 无法判断，需 l++ 退化处理。

排除法：「必须先排序」排序会丢失旋转信息、更慢；「只有一半能二分」两半都是候选，只是先定哪半有序；「最小值一定在中间」没有这回事，旋转点在哪最小值就在哪。

规则：按「a[mid] > a[r] 则最小值在右半」的规则逐轮排除，最终收敛到 0。

考点：旋转数组二分的标准模板追踪。

解析：l=0, r=6, mid=3：a[3]=7 > a[6]=2，最小值在右半，l=4；l=4, r=6, mid=5：a[5]=1 > a[6]=2 假，r=5；l=4, r=5, mid=4：a[4]=0 > a[5]=1 假，r=4；l=4, r=4 退出，输出 a[4] = 0。最小值在旋转点处。

排除法：4 是数组第一个元素不是最小值；2 是最后一个元素；7 是旋转点前的最大值。

规则：$1.5 \times 10^9 + 1.8 \times 10^9 = 3.3 \times 10^9 > 2.147 \times 10^9$，直接相加溢出；差值写法安全。

考点：防溢出 mid 的数值验证。

解析：l + r = 3300000000，超过 int 上限 $2147483647$，溢出后是错误值（可能为负）。而 r - l = 300000000，l + (r - l) / 2 = 1500000000 + 150000000 = 1650000000，全部在 int 范围内，恰好是下取整的平均数。这就是为什么竞赛代码统一用 l + (r - l) / 2。

排除法：$3.3 \times 10^9$ 明显超上限，「没超」错误；差值写法是最安全的；位运算只是另一种等价写法，不是必需。

规则：二分答案 = 在候选值轴上做「谓词二分」——check 的可行性单调时，分界点两侧一边全真一边全假，二分夹的就是这个分界点。

考点：二分答案的单调性论证。

解析：以切蛋糕为例：候选段长 x 越大能切出的段数越少，「能切出至少 k 段」随 x 增大从真变假，存在唯一分界点。二分每次用 mid 的可行性决定往哪半走，最终 lo == hi 落在分界点，即最优解。所以「单调性论证」不是锦上添花，是二分答案能工作的前提。

排除法：「换个名字」掩盖了本质差别——二分查找在数组下标上分、二分答案在值域上分；「排序后自然单调」排序是让下标有序，二分答案的单调来自问题本身（可行性随候选值变化）；「不用检查」错了，每个二分答案题第一件事就是确认 check 是否单调。

规则：最大化最小：答案越大越难可行，check 随候选值从真变假，用 l = mid（可行保大端）；最小化最大：答案越小越难可行，check 随候选值从假变真，用 r = mid（可行保小端）。

考点：check 难度方向与收缩方式配对。

解析：写 check 时问自己：「x 变大，这个条件更容易满足还是更难？」最大化最小值（跳石头：最短距离越大越难跳，可行 → 假）用 check(mid) 真时 lo = mid；最小化最大值（数列分段：段和上限越小越难分，可行 → 真随 x 增大从假变真）用 check(mid) 真时 hi = mid。两方向是镜像，背反了收敛到错误端。

排除法：「同一个 check」两方向语义不同，不能复用；「都用 l = mid」最小化最大必须 r = mid 保小；「返回真就行」方向错则答案错。