CSP-J 2024 第一轮 第 9 题：假设有序表中有1000 个元素，则用二分法查找元素x 最...

题目

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

选项

• A. 25
• B. 10
• C. 7
• D. 1

答案

B

题解

答案选 B．10。

二分查找每次与中间元素比较后，都会把查找范围缩小约一半。

最多比较 \(k\) 次，可以完成对最多 \(2^k-1\) 个元素的二分查找。因为：

• 比较 9 次：最多支持 \(2^9-1=511\) 个元素；
• 比较 10 次：最多支持 \(2^{10}-1=1023\) 个元素。

\(511<1000\le1023\)，所以最坏情况下需要比较 10 次。