浙江高考信息技术 · 浙江普通高等学校招生全国统一考试2016A 信息技术 第 12 题

【加试题】已知一无序数组a（下标1到n），通过引入数组b（下标1到n），使得a(b(1))≤a(b(2)) ≤a(b(3))……≤a(b(n))（示例如图所示），对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是 

这题考的是二分查找（对分查找）在特定有序序列上的应用。拿到题先别急着套公式，要反应过来：二分查找是对“有序数组”进行的，这里有序的不是原数组 a，而是通过数组 b 映射后得到的序列 a(b(1))...a(b(n))。所以中点位置要按 b 的索引来算，而中点值必须取映射后的 a(b(m))。

最容易掉进两个坑：一是把二分查找默认套在原数组 a 上，误以为中点就是 a 的下标，从而选成 a(m)；二是中点位置计算时，直接用 b(1) 和 b(n) 的平均值，忽略了 b 本身只是下标映射，真正的有序序列的下标依然是 1 到 n，所以中点位置必须用 Fix((1+n)/2)。这两个错误会导致选项 A、C、D 全错。

考点与概念

这道题考查二分查找（对分查找）算法的前提条件和具体实现细节。二分查找的核心前提是：查找的对象必须是一个有序序列。时间复杂度为 O(log n)，每次将搜索区间缩小一半。

命题视角

命题人这里玩了一个“障眼法”。题目给了一个无序数组 a，然后引入数组 b，构造出了一个新序列：S = a(b(1)), a(b(2)), ..., a(b(n))。题目明确说明这个新序列是有序的，并且要对这个有序序列进行二分查找。

很多学生看到“二分查找”就下意识地去找原数组 a 的下标，或者去算 b 数组下标的平均值，这就是掉进了命题人挖的坑。命题人想考察的是：你真正理解二分查找是对“有序数据”操作，而不是对“原始下标”操作。

思考与推导

拿到题，首先要明确二分查找的查找对象是谁。既然题目说对“这些有序数据”进行查找，那查找对象就是序列 S。

1. 确定查找范围的下标：在二分查找中，我们维护的是当前有序序列的起始下标 left 和结束下标 right。对于序列 S 来说，它的下标是从 1 到 n 的（因为 b 的下标也是 1 到 n）。所以，第一次查找时，left = 1, right = n。 2. 计算中点位置 m：根据二分查找的标准公式，中点位置 m = Fix((left + right) / 2)。代入 left 和 right，得到 m = Fix((1 + n) / 2)。 3. 确定中点值：既然 m 是序列 S 的下标，那么 S[m] 对应的就是原数组 a 中下标为 b(m) 的元素。所以，中点值应该是 a(b(m))。

逐项分析

• 选项 A：m 的计算是对的，但中点值写成了 a(m)。这是把 S 的下标当作了 a 的下标，错误。
• 选项 B：m = Fix((1+n)/2)，中点值 = a(b(m))。完全符合上述推导，正确。
• 选项 C：m 的计算变成了 (b(1)+b(n))/2。这是误以为二分查找是对 b 数组的下标进行二分，完全偏离了题意，错误。
• 选项 D：m 的计算同 C，也是错的。

避坑指南

一定要分清“原数组”和“有序序列”的区别。原数组 a 是无序的，不能作为二分查找的对象；真正有序的是通过 b 映射后形成的序列。中点位置永远是对有序序列的下标进行计算，而中点值则是通过该下标在 b 中查找到对应的 a 元素。

考频与趋势

根据历年浙江省高考信息技术真题数据，二分查找（对分查找）是高频考点，近五年在加试题中出现的频率约为 25%-30%。此类题目常以“已知有序序列”或“构造有序序列”为背景，考察学生对算法前提条件的理解。

预测

基于当前考频和命题风格，未来此类题目可能会继续以“映射有序”为切入点，或者结合其他数据结构（如链表、树）考察二分思想的变体。但核心逻辑不变：先确认有序序列的下标范围，再套用二分公式，最后正确映射回原数据。