NOIP 普及组初赛 · NOIP 2014 普及组初赛试题 第 18 题

设有 $100$ 个数据元素，采用折半搜索时，最大比较次数为( )。

这题考二分查找的最大比较次数。拿到题别急着套公式，先想：二分每次砍半，100 个元素要砍几次才能只剩 1 个？从 100→50→25→13→7→4→2→1，数一下步数就是答案，再验证 2^6=64<100≤2^7=128 也能说明问题。

学生容易把公式记成⌊log₂ n⌋，直接算出 6 就选了 A，这是最典型的坑。其实二分查找是区间减半，最后一次比较才能确定目标位置，所以必须 +1。还有人会数错步骤，从 100 开始往下数：100→50(1)→25(2)→13(3)→7(4)→4(5)→2(6)→1(7)，一共 7 次。如果误以为 2^6=64 已经覆盖 100，就会忽略第 7 次比较，导致错误。

这题考什么

这道题考查二分查找（折半搜索）的最大比较次数。这是数据结构里的经典结论：在有序数组中，二分查找最坏情况下需要比较的次数等于将区间不断对半缩小，直到只剩一个元素为止的步数。

概念讲人话

二分查找的核心是：每次把搜索范围缩小一半。比如从 100 个元素开始，第一次比较后剩下 50 个，第二次 25 个，第三次 13 个……一直这样砍，直到剩下 1 个元素，这时候再比较一次就能确定目标是否存在。所以“最大比较次数”就是看需要砍多少次才能把 100 变成 1。