深耕专业教研，探索前沿技术
信息技术来源：浙江省县域教研联盟高三年级5月高考模拟考试

第 7 题

答案与解析

本题解析

参考答案

B

程序分析

left←0,right←5,c←0
left≤right?
Y → mid←[(left+right)/2] → c←c+1 → key=a[mid]?
    Y → 输出c
    N → key>a[mid]?
        Y → left←mid+1 → 返回left≤right?
        N → right←mid−1 → 返回left≤right?
N → 输出c

left和right给出当前查找区间的两端下标，初始区间为[0,5]。每轮取中点mid后，先执行c←c+1，再判断是否找到key，因此c记录访问中点元素的次数，找到目标的那一轮也计入。

若key等于中点元素，立即输出c；若key较大，则排除中点及其左侧部分，否则排除中点及其右侧部分。更新后若left>right，说明区间已空，也会输出c。因此，输出2既可能是第2轮查找成功，也可能是第2轮之后区间变空。

解题思路

数组中的元素按升序排列，流程每轮取查找区间的中点，并根据key与中点元素的大小关系缩小区间，这是对分查找。

初始mid=(0+5)//2=2，第1轮访问a[2]=y。若key=y，当轮就结束，c=1；要使c=2，必须继续向左或向右查找。

第1轮后的情况 第2轮访问位置 第2轮后结束的条件 其他情况
key<y，区间变为[0,1] mid=0，访问x key=x时找到；key<x时right变为−1，区间为空 x<key<y时区间变为[1,1]，还要访问37
key>y，区间变为[3,5] mid=4，访问75 key=75时找到 key<75时还要访问64；key>75时还要访问96

由于x<y，左侧能在第2轮结束的范围为key≤x；右侧只有key=75能在第2轮结束。合并得到key≤x或key=75，对应B。