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

【加试题】数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：

i = 1: j = 10
Key = Val(Text1.Text)
Do While i <= j
    m = (i + j) \ 2
    If a(m) = Key Then Exit Do 'Exit Do表示退出循环
    If Key Mod 2 = 1 And a(m) Mod 2 = 0 Then
        （1）
    ElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 Then
        （2）
    Else
        （3）
    End If
Loop
If i > j Then s = "没有找到！" Else s = "位置：" + Str(m)
Text2.Text = s

上述程序中方框处可选语句为： ①i = m + 1 ②j = m - 1 ③If Key < a(m) Then j = m - 1 Else i = m + 1 则（1）、（2）、（3）处语句依次是

这题考二分查找的变体，核心是判断：二分中间点m的奇偶性与Key的奇偶性是否一致，一致则继续在该半区找，不一致则直接跳到另一半区。

学生容易把普通二分查找的左右区间移动逻辑直接套用过来，忽略了数组的特殊结构（奇数在前、偶数在后）。当Key是奇数而m是偶数时，Key一定在m右侧，若仍按普通二分把j移到m-1就会错过答案；反之亦然。另外，很多人看到Else分支就以为是大数在前、小数在后，其实这里Else表示奇偶性相同，必须根据大小关系继续二分，不能直接跳过。

这道题考查的是二分查找（对分查找）在特殊排序数组中的应用。数组a的特点是：所有奇数在前且升序，所有偶数在后且升序。也就是说，数组整体并不是单调递增的，但奇数区间和偶数区间各自是单调的。命题人故意用这个结构来挖坑：如果只用普通的二分查找，一旦中间点m的奇偶性与Key不一致，就无法判断Key在m的左边还是右边，必须根据奇偶性直接跳到另一半区。因此，题目给出的三个空分别对应三种情况：Key是奇数而m是偶数、Key是偶数而m是奇数、Key与m奇偶性相同。思考心法就是：拿到题先判断Key和a(m)的奇偶性，如果不同，直接跳到对应的那一半；如果相同，再像普通二分那样比较大小决定左右区间。这样就能保证每次迭代都能把搜索范围缩小一半，最终要么找到Key，要么i>j说明没找到。现在逐空推导：第一个空对应Key是奇数且m是偶数的情况，此时Key一定在m的右侧，所以要把左边界i移到m+1，即选①；第二个空对应Key是偶数且m是奇数的情况，Key一定在m的左侧，所以要把右边界j移到m-1，即选②；第三个空对应Key与m奇偶性相同，这时候只能用普通二分的大小比较：如果Key<a(m)则j=m-1，否则i=m+1，即选③。因此三个空依次是①、②、③，对应选项C。避坑指南：很多同学会误以为Else分支是大数在前、小数在后，从而直接套用普通二分的逻辑，但这里Else表示奇偶性相同，必须根据大小关系继续二分，不能直接跳过。另外，如果忘记判断奇偶性而直接按大小移动区间，会在奇偶性不同的区域来回震荡，导致i和j永远不相交，最终输出错误结果。考频趋势方面，根据历年真题统计，二分查找及其变体在浙江高考信息技术卷中属于高频考点，近五年平均每年出现1-2次，其中纯二分查找（单调数组）占70%，变体二分（如本题的奇偶分块、旋转数组等）占30%。预测未来可能继续考查二分查找在不同排序结构中的应用，比如旋转数组、奇偶分块、或者带条件的二分（如查找第一个大于等于某值的元素）。暂无足够依据预测更具体的变体形式，但掌握二分查找的核心思想（每次将区间减半）和灵活判断左右区间的技巧是关键。