杭州网站如何制作,洛阳网站建设,网站模板免费下载php,山西网络推广哪家专业题目描述 在一个非降序列中#xff0c;查找与给定值最接近的元素。 输入格式 第一行包含一个整数n#xff0c;为非降序列长度。1 n 100000。 第二行包含n个整数#xff0c;为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。 第三行包含一个整数m#x…题目描述 在一个非降序列中查找与给定值最接近的元素。 输入格式 第一行包含一个整数n为非降序列长度。1 n 100000。 第二行包含n个整数为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。 第三行包含一个整数m为要询问的给定值个数。1 m 10000。 接下来m行每行一个整数为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。 输出格式 m行每行一个整数为最接近相应给定值的元素值保持输入顺序。若有多个值满足条件输出最小的一个。 样例输入 3 2 5 8 2 10 5 样例输出 8 5
解题思路: 经过二分查找后low和high分别会指向比 x 大和比 x 小的元素计算这两个元素到 x 的距离返回更小的那个元素值不清楚的话可以在代码中打印出经过循环后的low和high值。 注意边界的情况 假设列表是 [2,5,8] 例如查找的是10low最后为3high为2此时直接返回列表最后一个元素即可 如果查找的是-1high最后的取值为-1low为0此时直接返回列表第一个值即可。
# 数据的输入
n int(input())
list1 list(map(int, input().split()))
m int(input())def find_closest(li, x):low 0high len(li) - 1while low high:mid (low high) // 2if list1[mid] x:return list1[mid]elif list1[mid] x:low mid 1else:high mid - 1# 经过二分查找后low和high分别会指向比 x 大和比 x 小的元素# 计算这两个元素到 x 的距离返回更小的那个元素值if low len(li):return li[-1]elif high 0:return li[0]elif abs(li[low] - x) abs(li[high] - x):return li[low]else:return li[high]for i in range(m):x int(input())print(find_closest(list1, x))
