python - 在 python 中查找另一个项目最接近列表中哪两个元素的最快方法

Question

输入是一个排序的元素列表和一个外部项。例如:

list_ = [0, 3.5, 5.8, 6.2, 88]
item = 4.4

找出 list_ item 中的哪两个元素介于两者之间的最快方法是什么？例如，在这种情况下，这两个数字将是 3.5 和 5.8。有什么想法吗？

Answer 1

由于输入已排序，您最好在算法上打赌是使用 bisect 模块——例如bisect_left

>>> list_ = [0, 3.5, 5.8, 6.2, 88]
>>> item = 4.4
>>> bisect.bisect_left(list_, item)
2

您想要的项目位于索引 bisect_left(list_, item) 和
bisect_left(list_, item) - 1

这应该会为您提供 O(logN) 次搜索的结果——从算法的角度来看，它并没有比这更好。