1

我正在寻找平均案例性能为 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))，并且排序只会进行一次。

4

1 回答 1

2

这似乎有效：

>>> 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可能使用 C 实现，bisect这将比您在纯 Python 中编写的任何内容都快，因此即使进行较少的比较，纯 Python 解决方案也可能会更慢。

您可以稍微优化将参数j传递给的搜索：lobisect

j = bisect.bisect(L, max, i)
于 2012-11-22T07:42:13.997 回答