给定一个浮点数，查找列表中是否存在或其最接近的数

Question

我有一个包含元组的列表，这些元组是二维的，里面有x和y的值。我们把这个列表叫做data。我想要输入两个浮点数，xmin和xmax，然后返回在这个区间内y值最大的那个点的索引。即使xmin和xmax不完全对应数据点，它也应该能正常工作。

我知道怎么解决这个问题，但我不知道怎么把xmin和xmax四舍五入到列表中最接近的值。因为我还是个Python新手，所以对此没有头绪。

# Find the index of the point (x, y) with the maximum y value
# on the interval [xmin, xmax]
def find_peak(data, xmin, xmax):

我暂时可以遍历这个列表，记录每个x值的最小差异。这样可行吗？还是说有更聪明的方法？

Answer 1

max_finder = lambda point: point[1] if x_min <= point[0] <= x_max else float("-inf")
# get data point of target element
max_y = max(data, key=max_finder)

# gets index of target element
max_y_idx = max(enumerate(data), key=lambda x: max_finder(x[1]))[0]
# or alternatively, after finding max_y
max_y_idx = data.index(max_y_idx)

请注意，这种方法的效率应该会稍微好于排序的其他方法，因为 max 的复杂度是 O(n)，而 index 在最坏情况下也是 O(n)，相比之下，排序的复杂度是 O(n*log(n))。

有关详细信息，请参考 max 和 enumerate 的文档。

Answer 2

给定一组二维坐标。

1. 首先，根据x坐标对这些数据进行排序。这个排序要像平常我们排队那样自然。
2. 接着，使用Python的bisect模块来找出数据点的开始和结束索引。
3. 然后，利用内置的min函数，配合operator.itemgetter(1)，在x_main和x_max之间找到y值最大的元素。

示例实现

def foo(data, x_min, x_max):
    from bisect import bisect_left, bisect
    from operator import itemgetter
    data = sorted(data)
    x_data = [x for x,y in data]
    index_min = bisect_left(x_data, x_min)
    index_max = bisect(x_data, x_max)
    return max(data[index_min:index_max],key=itemgetter(1))[-1]

示例运行

>>> data = [(random.randint(1,20),random.randint(1,20)) for _ in range(10)]
>>> data
[(9, 9), (11, 11), (7, 7), (16, 11), (15, 19), (8, 18), (16, 3), (18, 7), (17, 13), (3, 11)]
>>> foo(data,3,7)
11