深耕专业教研，探索前沿技术
信息技术来源：浙江强基联盟2026年3月高三联考

第 12 题

答案与解析

本题解析

参考答案

C

解题思路

程序反复取查找区间的对分点m，并根据a[m]与x的比较结果移动左右边界，采用了对分查找。

程序分析

g = [0, 4, 7, 10]
x = random.randint(22, 24)
count = 0
for i in range(len(g) - 1):
    L, R = g[i], g[i+1] - 1
    ans = g[i] - 1
    ...

randint(22, 24)包含两端，因此x只可能为22、23、24。由L、R的赋值可知，g把a分为下标0～3、4～6、7～9三段，分别是[15, 23, 23, 30]、[10, 25, 35]、[12, 18, 22]。每段均按非降序排列，可以分别进行对分查找。每段开始时，ans先置为该段起点的前一位。

while L <= R:
    m = (L + R) // 2
    if a[m] < x:
        ans = m
        L = m + 1
    else:
        R = m - 1

若 a[m] < x，就把 m 记入 ans，并继续向右查找，以寻找下标更大的满足条件的元素；否则 a[m] 及其右侧元素都不小于 x，只需继续向左查找。区间为空时，ans 即该段最后一个小于 x 的元素下标；若一个也没有，ans 保持为该段起点的前一位。

count += (ans - g[i] + 1)

每段有序，小于 x 的元素从该段起点连续排列到 ans，因此数量为 ans - g[i] + 1；没有符合条件的元素时该式为 0。将三段的数量累加，count 就是整个列表中严格小于 x 的元素个数。

按已经确定的统计功能，只需覆盖 x 的全部三个取值：

x 第一段小于 x 的个数 第二段小于 x 的个数 第三段小于 x 的个数 count
22 1 1 2 4
23 1 1 3 5
24 3 1 3 7

当 x 从 23 变为 24 时，第一段中的两个 23 同时计入，count 从 5 直接增加到 7。