CSP-J 2026 第一轮 第 12 题：在含 1000 个互不相同元素的升序数组中

题目

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

选项

• A. 500
• B. 9
• C. 11
• D. 10

答案

D

题解

答案是 D. 10 次。

二分查找每次与中间元素比较，若没有找到，就把查找范围缩小约一半。最坏情况下，剩余元素数量依次为：

``text 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0 ``

每个箭头对应一次比较，共 10 次。注意：只剩 1 个元素时，还需要再比较一次，才能确定找到或不存在。

也可以用公式计算： \[ \lfloor \log_2 1000 \rfloor+1=9+1=10。 \]