CSP-J 入门级 · CSP 2024 入门级第一轮 第 9 题

假设有序表中有 $1000$ 个元素，则用二分法查找元素 $X$ 最多需要比较（ ）次。

这道题考二分查找的最坏比较次数。拿到题先想：有序表二分就是把范围对半砍，最多砍几次能把1000个元素砍到0？其实就是要找最小的k，让2的k次方大于等于1000。

容易把比较次数想成log2(1000)≈9.97然后四舍五入成10，或者误以为只要log2(n)就行。命题人喜欢挖这里：二分查找每次比较后区间减半，最坏情况是直到区间为空才确定没找到，所以次数是ceil(log2(n+1))，不是ceil(log2(n))。比如n=1时也要1次比较，n=2时也要2次，n=3时也要2次，n=4时也要3次——都是找2^k≥n+1的最小k。

考点定位

这道题考的是二分查找的最坏比较次数。它属于算法基础里的经典计算题，命题人常把它放在单选题里，让你直接填数字，不让你写代码。

概念说人话

二分查找的核心就一句话：有序表里，每次把当前区间对半砍，用中间那个元素跟你要找的X比一比，比大了X就在左半边，比小了X就在右半边，区间直接减半。重复这个过程，直到区间里没元素了，说明X不在里面。

最多比较几次？ 就是看最倒霉的情况：每次砍完区间都还剩下至少一个元素，直到最后一次砍完区间才变成空。数学上能证明，这个次数等于最小的k，满足

\[2^k \ge n+1\]

或者写成向上取整的形式：\(\lceil \log_2(n+1) \rceil\)。记住这个公式，后面做题就不会乱套。