是否存在允许有效范围查询的python数据结构？

Question

说,你有一个整数列表,例如

foo = [3,9,23,54,77,123,...]

是否存在允许查询的高效数据结构

x = everything in foo between 10 and 100

以便

x == [23,54,77]

或x =一切<50

给

x = [3,9,23]

等等？

Answer 1

假设这些整数已经排序,它不是您想要的数据结构,而是一种算法:即二进制搜索.在Python中,这是由bisect模块提供的.

因此,例如,要查找小于50的所有成员:

from bisect import bisect_left
i = bisect_left(foo, 50)
result = foo[:i]