CSP-J 入门级 · CSP 2019 入门级第一轮 第 5 题

设有 $100$ 个已排好序的数据元素，采用折半查找时，最大比较次数为（）

这题考二分查找最坏比较次数，核心是找2的幂次覆盖n。直接看2^6=64<100≤128=2^7，所以是7次。

很多同学会算成6次，因为log2(100)≈6.64，下意识取整得6，忘了最坏情况要+1；或者混淆向上取整和向下取整的公式适用场景，把⌊log₂n⌋+1错写成⌈log₂n⌉，导致答案偏差。

考点与概念：二分查找每次把区间折半，最坏比较次数取决于区间大小n。若n在2^k与2^(k+1)之间（即2^k < n ≤ 2^(k+1)），则最多需要k+1次比较。公式可记为⌊log₂n⌋+1，也可理解为“找到最小的k使2^k ≥ n，k即为答案”。

命题人挖坑点：这道题特意选100这个数，因为它卡在2^6=64和2^7=128中间，容易让人只算log₂100≈6.64就停手，误选6；或者把公式记混，用⌈log₂n⌉算出7，却忘了这是针对n+1的情况（⌈log₂(n+1)⌉才是等价形式）。命题人就是想看你是否真正理解“区间缩小到1个元素才算找到”的边界。

思考心法：拿到题先想“2的幂次表”，心算2^6=64，2^7=128，100落在64到128之间，说明6次不够，得7次。验证一下：第1次剩50，第2次25，第3次13，第4次7，第5次4，第6次2，第7次1——确实7次才能确定。公式代入⌊log₂100⌋+1=6+1=7，完美吻合。

避坑提醒：千万别直接写log₂100≈6.64就选6，那是忽略了“最坏情况”必须取整加1；也别硬套⌈log₂n⌉，那是针对n+1的等价变形，用错会偏。记住：2^k < n ≤ 2^(k+1) ⇒ k+1次。

考频与趋势：二分查找在题库里共考过39题，覆盖7个级别，从2008年到2026年逐年都有出现，2024年考了9题、2025年7题、2026年5题，属于高频考点。分赛事看，GESP五级16题、七级7题、六级1题，CSP入门级5题、提高级5题，NOIP初赛共5题。说明低级别和初赛更爱考这种纯概念计算题，高级别可能结合实现细节。

预测：基于近年数据，二分查找在GESP五级和CSP入门级仍会高频出现，大概率继续以“给定n求最坏比较次数”或“给定比较次数反推n的范围”这类单选题形式考察，数字会选在2的幂次附近（如100、199、300等）来挖坑。暂无足够依据预测是否会转向实现题或动态区间变种。