使用预处理在O(1)时间内找到数组中最接近的数字

Question

问题陈述

我有一个排序的整数数组arr = [1, 5, 7, 8, 9]以及一个整数target。数组arr不会更改。

我希望在target中找到与arr最接近的值。

例如:说target = 4。那么，答案将是5。这是因为abs(target - 5)小于target与所有其他数字之间的距离。

一种太慢的方法

如果没有预处理，一种有效的方法就是应用二进制搜索，例如使用来自std::lower_bound标准库的std::upper_bound和C++。这将在O(log(n))时间中找到结果。

但是O(log(n))是，不足以满足实时需求的。

问题--这能用预处理来优化吗？

我将在不变的数组target上运行具有不同值的arr的多个查询。我如何预处理数据(不管时间复杂度如何)，以便为任何target找到与target在恒定时间(O(1))最近的值？或者说这是可能的？

注意，数组中的数字可能非常大(10^9)，因此我们不能提前计算每个target变量的结果并将其存储在字典中。

Answer 1

用numpy怎么样？

import numpy as np
arr = np.array([1, 5, 7, 8, 9])
target = 4
arr[abs((arr - target)).argmin()]

编辑。此代码中的目标是可变的。检查以下函数。

import numpy as np
def closet_number(arr, target):
    arr = np.array(arr)
    return arr[abs((arr - target)).argmin()]

closet_number([1,5,7,8,9], 4)