使用三元搜索來查找範圍內的所有元素？

我正在尋找算法被O的平均情況下的性能（日誌（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））是非常優選的，並且該排序將只進行一次。

來源

2012-11-22 Nuclearman

我不明白你的推理*「以來的最小和最大值實際上可能沒有在列表中，或者甚至重複，二進制搜索將不會執行「*」。你能詳細說明一下嗎？ – NPE

它需要是帶有內存的二進制搜索。「記住，你有最後一個值。如果你是即將返回‘未發現價值’，在你的記憶返回一個值」 – inspectorG4dget

在下面的例子中，該算法的目的是最小和最大的列表中返回的所有值值。低效率的方式做同樣的事情是：[X在列表中移除x當x> =分鐘且x <=最大值] – Nuclearman

這似乎工作：

>>> 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（日誌（N））。還要注意的是bisect可以用來bisect C實現，這將是比任何你可以在純Python寫的快，所以一個純Python的解決方案可能會慢一些，即使這樣做少一點攀比。

你可以爲j傳遞lo參數bisect略微優化搜索：

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

來源

2012-11-22 07:42:13 Bakuriu

這可能是什麼我要找的。我會看看是否有其他方法出現，無論哪種方式，該模塊看起來對於我正在處理的與此問題有關的其他內容有用。 – Nuclearman

使用三元搜索來查找範圍內的所有元素？

回答

相關問題