简答题 偏难
#15430

二分查找 小明在学习二分查找后,编写程序实现查找key所遍历的过程。如有原始数据是 12, 18, 27, 31, 46, 68, 75, 80, 90, 92…

二分查找

小明在学习二分查找后,编写程序实现查找key所遍历的过程。如有原始数据是 12, 18, 27, 31, 46, 68, 75, 80, 90, 92,待查找的数据是90,打印输出key所遍历数分别是:

46,80,90。他编写的程序如下,完善划线处的代码。

def dfsearch(data,key): #二分法在data中查找key

p = [] #存放key所遍历数

flag = False

i,j = 0,len(data) - 1

while i <= j:

m = (i+j)//2

p.append(data[m])

if         ①        :

flag = True

return p,flag

elif data[m] > key:

j =         ②

else:

i =         ③

return p,flag

data = [12,18,27,31,46,68,75,80,90,92]

key = int(input())

rst,flag =         ④

if flag:

print('原始数据是',data,'待查找的数据是',key,'\n找到,查找的数分别是:')

for i in rst:

print(i,end = ',')

else:

print('原始数据是',data,'待查找的数据是',key,'\n没有找到,查找的数分别是:')

for i in rst:

print(i,end = ',')

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false;">def dfsearch(data,key):#二分法在data中查找key     p = []#存放key所遍历数     flag = False     i,j = 0,len(data) - 1     while i &lt;= j:         m = (i+j)//2         p.append(data[m])         if data[m] == key:             flag = True             return p,flag         elif data[m] &gt; key:             j = m - 1         else:             i = m + 1     return p,flag data = [12,18,27,31,46,68,75,80,90,92] key = int(input())     rst,flag = dfsearch(data, key) if flag:     print('原始数据是',data,'待查找的数据是',key,'\n找到,查找的数分别是:')     for i in rst:         print(i,end = ',') else:     print('原始数据是',data,'待查找的数据是',key,'\n没有找到,查找的数分别是:')     for i in rst:         print(i,end = ',')</pre>
解析

确定二分查找的中间索引计算方式;每次循环计算中点位置并将该位置值加入遍历记录;比较中点值与目标值决定搜索区间:若相等则查找成功并返回;若中点值大于目标值则调整右边界;若中点值小于目标值则调整左边界;循环直到区间无效;最后根据返回标志判断是否找到目标。输入目标值后调用函数获取遍历序列和查找结果,按格式输出过程数据。