CSP-J 2019 第一轮 第 5 题：折半查找最大比较次数

题目

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

选项

• A. 7
• B. 10
• C. 6
• D. 8

答案

A

题解

选 A. 7。

折半查找每比较一次，就能将待查找范围缩小约一半。对于 \(n\) 个有序元素，最大比较次数为： \[ \lfloor \log_2 n\rfloor+1 \]

因为 \(2^6=64\le100<128=2^7\)，所以： \[ \lfloor\log_2 100\rfloor+1=6+1=\boxed{7} \]

注意：范围缩小到只剩 1 个元素时，仍然需要比较一次。