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

对于已排序的列表，如何找到接近给定数字的最小数字？

例如，

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

如何找到小于或等于700的最大元素quickly？ （如果我有1000万个元素，那么线性搜索会很慢）。在本例中，答案是 645。

您可以使用bisect module:

import bisect

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

location = bisect.bisect_left(data, 700)

result = data[location - 1]

这是标准库中的一个模块，将使用二分查找找到想要的结果。根据您需要的确切值，您也可以使用bisect_right代替bisect_left.

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