CSP-J 入门级 · CSP 2026 入门级第一轮 第 12 题

【单选】在含 1000 个互不相同元素的升序数组中，用二分法查找给定值（返回元素位置或报告不存在），最坏情况下需要与数组元素比较多少次（ ）。

二分查找的判定树是近似完全二叉树，最坏比较次数 = ⌊log₂n⌋ + 1；这里 n=1000，2^9 = 512 < 1000 ≤ 1024 = 2^10，所以是 10 次。

用 ⌈log₂n⌉ 算成 9（当 n 恰好是 2 的幂或接近时容易差 1）；或凭感觉选 500（把二分当成线性查找）。

解析

本题考查二分查找的比较次数与判定树高度。

为什么是 ⌊log₂n⌋ + 1

二分查找每比较一次，候选区间长度约减半；若把查找过程画成一棵判定树（每个内部结点是一次比较），树高就是最坏比较次数。长度为 n 的判定树高度为：

最坏比较次数 = ⌊log₂ n⌋ + 1

n = 1000 时：2^9 = 512 < 1000 ≤ 1024 = 2^10，所以 ⌊log₂1000⌋ = 9，最坏比较次数 = 9 + 1 = 10，选 D。

用最坏情形验证

以"查找不存在的元素"为最坏情形。每次比较把区间一分为二：

1000 → 500 → 250 → 125 → 62（含中点） → 31 → 15 → 7 → 3 → 1 →（区间为空，报告不存在）

区间长度序列中，只要长度 > 1 就必须继续比较，长度降到 1 时还要比较这最后 1 个元素才能判定： 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1 共 10 步；最后空区间再判一次即得出"不存在"。 按"每次比较后区间减半"统计，比较次数为 10 —— 与公式一致。

其他选项为什么错

• B. 9：等于 ⌈log₂1000⌉ = 10 取整出错，或误用"树高 = ⌊log₂n⌋"，漏掉首次比较；
• C. 11：把 1000 当成需要 2^11 覆盖（实际 2^10 = 1024 已足够）；
• A. 500：把二分退化成了顺序查找。

记忆点

• 判定树有 n 个内部结点、n+1 个失败结点（叶子），高度 h 满足 h ≥ ⌈log₂(n+1)⌉，对 n = 1000 即 h ≥ 10；
• 二分查找的时间复杂度 Θ(log n)，前提是序列有序且支持随机访问（数组可以，链表不行）；
• 常见变形：n = 1024 时最坏 11 次？错——⌊log₂1024⌋ + 1 = 10 + 1 = 11 次（因为要比较到最后一层）。用公式算最保险。