python - 使用三元搜索查找范围内的所有元素？

Question

我正在寻找平均情况下性能为 O(log(N)) 的算法，以从排序列表中提取介于(或等于)最小值和最大值之间的元素。

问题在于，由于最小值和最大值实际上可能不在列表中，甚至可能不重复，因此二分查找不起作用。三元搜索似乎更接近我所寻求的，但到目前为止，我还无法创建一个函数来完成我所看到的基于三元搜索的功能。

例如输入:

list=[1,2,3,4,5,6,7], min=3, max=6

应该返回 [3,4,5,6]。同样，

list=[500,757,2412,10000,123123], min = 600, max = 5000

应该返回 [757,2412]。

这也可以在 python 中使用效率较低的方式完成:

def withinRange(values,min,max):
   return [val for val in sorted(values) if val <= max and val >= min]

该操作被调用得足够多，以至于 O(log(N)) 是非常优选的，并且排序只会进行一次。

Answer 1

这似乎可行:

>>> import bisect
>>> def bin_slice(L, min, max):
...     i = bisect.bisect_left(L, min)
...     j = bisect.bisect(L, max)
...     return L[i:j]
... 
>>> bin_slice([1,2,3,4,5,6,7,8,9], 3, 6)
[3, 4, 5, 6]
>>> bin_slice([500,757,2412,10000,123123], 600, 5000)
[757, 2412]

复杂度类似于 2log(N)，即 O(log(N))。另请注意，bisect 可能会为 bisect 使用 C 实现，这将比您用纯 python 编写的任何东西都快，因此纯 python 解决方案甚至可能更慢如果比较少一点。

您可以稍微优化对 j 的搜索，将 lo 参数传递给 bisect:

j = bisect.bisect(L, max, i)