从整数列表中，获取最接近给定值的数字

Question

给定一个整数列表，我想找到哪个数字与我在输入中提供的数字最接近：

>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> takeClosest(myList, myNumber)
...
4

有什么快速的方法可以做到这一点吗？

Answer 1

如果不确定列表是否已排序，则可以使用内置min()函数，查找与指定数字之间的最小距离的元素。

>>> min(myList, key=lambda x:abs(x-myNumber))
4

请注意，它也可用于带有int键的字典，例如{1: "a", 2: "b"}。此方法花费O（n）时间。

如果列表已经排序，或者您可以只对数组进行一次排序，请使用@Lauritz答案中所示的二等分方法，该方法只需要O（logn）时间（但请注意，检查列表是否已排序为O） （n），排序为O（n log n）。）

我将重命名该函数take_closest以符合PEP8命名约定。

如果您是说要快速执行而不是快速编写，min那么除非是在一个非常狭窄的用例中，否则不应将其作为选择的武器。该min解决方案需要检查列表中的每一个数字，并做到每个号码的计算。使用bisect.bisect_left替代几乎总是更快。

“几乎”来自bisect_left要求对列表进行排序才能工作的事实。希望您的用例能够对列表进行一次排序，然后再将其保留。即使不是，只要您不需要在每次调用之前进行排序take_closest，该bisect模块就可能排在最前面。如果您有疑问，请尝试两种方法并查看实际差异。

from bisect import bisect_left

def take_closest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.

    If two numbers are equally close, return the smallest number.
    """
    pos = bisect_left(myList, myNumber)
    if pos == 0:
        return myList[0]
    if pos == len(myList):
        return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before

Bisect的工作方式是反复将列表减半，然后myNumber通过查看中间值来找出必须放入的一半。这意味着它的运行时间为O（log n），而不是最高投票答案的O（n）运行时间。如果我们比较这两种方法并同时提供一个sorted ，则结果如下：myList

$ python -m timeit -s "
from closest import take_closest
from random import randint
a = range(-1000, 1000, 10)" "take_closest(a, randint(-1100, 1100))"

100000 loops, best of 3: 2.22 usec per loop

$ python -m timeit -s "
from closest import with_min
from random import randint
a = range(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))"

10000 loops, best of 3: 43.9 usec per loop

因此，在此特定测试中，bisect速度快了将近20倍。对于更长的列表，差异会更大。

如果我们通过消除myList必须排序的前提条件来公平地竞争该怎么办？假设我们在每次 take_closest调用时对列表的副本进行排序，而min解决方案保持不变。使用上述测试中的200个项目列表，该bisect解决方案仍然是最快的，尽管只有30％。

考虑到排序步骤为O（n log（n）），这是一个奇怪的结果！唯一min仍然失败的原因是，排序是在高度优化的C代码中完成的，而min必须为每个项目调用lambda函数。随着myList尺寸的增加，min解决方案最终将更快。请注意，min为了赢得解决方案，我们必须堆叠所有有利条件。