查找列表中哪两个元素最接近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)搜索结果- 从算法的角度来看,它没有比这更好.