python-3.x - 我有一种简单的方法可以将数字分类到不同的范围吗？

Question

有一个清单：

ranges = [(0,11), (11, 20), (20, 35), (35, 40), (40, 50), (50, 62), (62, 
75), (75, 83), (83, 90), (90, 100)]

例如，(7, 8) 表示 7<=x<8。现在有一个数字 n，我想将它分类为不同的范围。

我在想：

ranges = [(0,11), (11, 20), (20, 35), (35, 40), (40, 50), (50, 62), (62, 
75), (75, 83), (83, 90), (90, 100)]
n = 22
for pair in ranges:
   if pair[0] <= n < pair[1]:
   print(f'{n} in the range：{pair}')

这个的时间复杂度是O(n)，但是如果有一个要分类的数字列表，时间复杂度就变成了O(m*n)。在这种情况下，我们是否有一种简单的方法可以使时间复杂度为 O(m)？

任何答案都值得赞赏。

标签： python-3.x

Answer 1

我认为 O(m) 不可能，但是 O(mlogn) 可以通过二进制搜索（而不是你建议的线性搜索）来管理，因为你的范围列表是“排序的”

而且 O(mlogn) 仍然是可扩展的，因为 log 函数对于大 n 增长非常慢，在这种情况下，logn 和常数之间没有太大区别。