python - 如何有效地在大型排序数组中找到最接近另一个值 X 的值

Question

对于一个排序列表，我怎样才能找到接近给定数字的最小数字？

例如，

mysortedList = [37, 72, 235, 645, 715, 767, 847, 905, 908, 960]

如何快速找到小于或等于 700 的最大元素？ (如果我有1000万个元素，那么线性搜索会很慢)。在这个例子中，答案是 645。

Answer 1

您可以使用 bisect模块:

import bisect

data = [37, 72, 235, 645, 715, 767, 847, 905, 908, 960]

location = bisect.bisect_left(data, 700)

result = data[location - 1]

这是标准库中的一个模块，它将使用 binary search找到想要的结果。根据您需要的确切值，您还可以使用 bisect_right而不是 bisect_left .

这比遍历列表更快，因为二分搜索算法可以跳过不包含答案的部分数据。这使得它非常适合在已知数据已排序时查找最近的数字。