A17882. 二分查找小明在学习二分查找后，编写程序实现查找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 = Fa…
填空题
较难
知识点
题目描述
二分查找
小明在学习二分查找后，编写程序实现查找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 = ',')参考答案
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 data[m] == key:
flag = True
return p,flag
elif data[m] > 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 = ',')答案解析
确定二分查找的中间索引计算方式；每次循环计算中点位置并将该位置值加入遍历记录；
比较中点值与目标值决定搜索区间：若相等则查找成功并返回；若中点值大于目标值则调整右边界；
若中点值小于目标值则调整左边界；循环直到区间无效；
最后根据返回标志判断是否找到目标。输入目标值后调用函数获取遍历序列和查找结果，按格式输出过程数据。
上一题
下一题