深耕专业教研，探索前沿技术
信息技术来源：浙江七校2026年普通高等学校招生全国统一考试模拟考试

第 12 题

答案与解析

本题解析

参考答案

B

解题思路

数组a按非递增顺序排列。程序每轮取区间[i,j]的中点m，再用i=m+1或j=m-1缩小区间，采用对分查找结构。与找到相等元素就结束的写法不同，本题在a[m]=key时仍向左继续查找，直到i>j。

程序分析

q = [0] * (len(a)+1)
L = R = len(a)//2
i, j = 0, len(a)-1
while i <= j:
    m = (i+j)//2
    if a[m] > key:
        i = m+1
        R += 1; q[R] = m
    else:
        j = m-1
        L -= 1; q[L] = m
print(q[L:R+1])

q初始全为0，L=R=4。当a[m]>key时，向右缩小查找区间，并先将R加1，再把下标m写到q的右侧；否则向左缩小查找区间，并先将L减1，再把m写到q的左侧。L、R由此分别标记已使用区段的左、右边界。

左右边界都在移动后才写入，因此初始位置q[4]一直保留0。最终切片包含这个0：它左侧是向左查找时记录的下标，按记录时间倒序排列；右侧是向右查找时记录的下标，按记录时间顺序排列。这里保存的是下标m，不是a[m]的值；下标0也可能被记录，要与初始保留的0区分。

选项分析

A

可能。取key=18，依次访问下标3、1、0：17≤18，记录3到左侧；18≤18，再把1记录到左侧；20>18，把0记录到右侧。区间变空后输出[1,3,0,0]。

B

不可能。[6,0,3,5]中间的0是初始保留值，右侧的3、5要求在这两处均向右查找，左侧的6要求随后向左查找。访问下标5时，a[5]=12，向右须满足key<12；访问下标6时，a[6]也为12，向左却须满足key≥12，两个条件矛盾。

C

可能。取key=12，访问下标依次为3、5、4：17>12，将3记录到右侧；后两处的值都为12，均向左查找，依次将5、4记录到左侧。输出[4,5,0,3]。

D

可能。取key=11，访问下标依次为3、5、6、7：前三处的值都大于11，依次将3、5、6记录到右侧；最后a[7]=11，向左查找，将7记录到左侧。输出[7,0,3,5,6]。