Python X轴最近点

Question

我正在尝试设计一个简单的算法，不用导入任何模块。假设你有几个在x轴上的点，比如：

d = [-5, -3.5, -2.8, -0.6, 1.2, 3.4, 5.6]

然后你让用户输入一个特定的点，程序应该返回离用户输入的值最近的那个点。因为可能会有负值，所以我只需要一个大概的思路。

Answer 1

min(array, key=lambda x: abs(x)-point)

上面的代码的作用是计算每个点的绝对值，然后找出这些绝对值中的最小值，再把用户输入的点从这个最小值中减去。

Answer 2

步骤有两个：

1. 使用 bisect 模块 来找到离目标值最近的较小值的索引。
2. 计算这个较小值和下一个较大值之间的绝对距离，然后从这两个值中选择一个。

这个方法的效率是 O(logN)，也就是说，对于 N 个点，最多只需要执行 log N 步。相比之下，如果用绝对距离来排序，找到最近的点需要 O(NlogN) 的时间，使用 min() 函数则需要 O(N) 的时间。

需要注意的是，第一步可能会选择到开始或结束的索引，这时候可能没有更小或更大的第二个点：

import bisect

def nearest(x, d):
    index = bisect.bisect(d, x)
    if not index:
        return d[index]  # left-most x coordinate
    if index == len(d):
        return d[-1]  # right-most x coordinate
    return min(d[index - 1:index + 1], key=lambda v: abs(v - x))

示例：

>>> import bisect
>>> def nearest(x, d):
...     index = bisect.bisect(d, x)
...     if not index:
...         return d[index]  # left-most x coordinate
...     if index == len(d):
...         return d[-1]  # right-most x coordinate
...     return min(d[index - 1:index + 1], key=lambda v: abs(v - x))
... 
>>> d = [-5, -3.5, -2.8, -0.6, 1.2, 3.4, 5.6]
>>> nearest(10, d)
5.6
>>> nearest(-10, d)
-5
>>> nearest(0, d)
-0.6
>>> nearest(3, d)
3.4

为了完整性，min() 方法是：

min(d, key=lambda v: abs(v - x))