NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 10 题

对有序数组 $\{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100\}$ 进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（ ）。

拿到这种题别急着套公式，先在脑子里把数组想象成一棵判定树：中间那个数（56）是根，左右各分一半，再往下分，直到叶子。数清楚每层有多少个节点，乘以层数，加起来除以总数，这就是平均比较次数。

学生最容易犯两个错：一是把数组当成‘完全二叉树’去硬凑层数，以为11个元素能填满前4层（1+2+4+8=15），其实最后两层是空的，必须按真实的中点划分来画；二是算完总和后忘了除以元素个数，直接选33，或者除以错了（比如除以10）。还有少数人会混淆‘查找失败’和‘查找成功’，把空节点的深度也算进去，导致分子变大。记住，题目问的是‘等概率查找成功’，只算那11个真实存在的数。

二分查找平均长度

有序数组长度11，等概率查找。

构造二分查找判定树（比较次数=深度）：

• 第1层（1次）：1个元素（位置6）
• 第2层（2次）：2个元素（位置3,9）
• 第3层（3次）：4个元素（位置1,4,7,10）
• 第4层（4次）：4个元素（位置2,5,8,11）

平均比较次数 = (1×1 + 2×2 + 3×4 + 4×4) / 11 = (1+4+12+16)/11 = 33/11

命题视角与考频趋势

这道题考的是二分查找的平均比较次数，属于基础算法概念，但命题人会特意选一个‘非完美二叉树’的节点数（11个），逼你动手画判定树或按中点递归数层，而不是死记公式。历年NOIP提高组初赛里，二分查找相关题目共出现过39次，覆盖从入门到提高、GESP五级至七级等多个级别，说明它一直是高频考点。具体到年份，2008年2题、2009年1题、2011年2题、2019年1题、2021年1题、2022年2题、2023年4题、2024年9题、2025年7题、2026年5题，还有5题年份未标注（null）。从分布看，近三年的题目数量明显上升（2024年9题、2025年7题），反映出命题组对二分查找及其变体（如判定树构造、平均/最坏比较次数）的考查力度在加大，尤其喜欢用‘非2^k-1’的节点数来制造陷阱。

预测

基于上述数据，未来两年（2027-2028）仍有较大概率出现二分查找相关题目，且很可能继续采用‘非完美树节点数’的设定，要求考生手动构造判定树或按中点递归计算各层节点数。不过，由于现有数据中缺少2027及以后的具体年份分布，无法精确预测出题形式或难度变化，故暂无足够依据预测更具体的考题形态。