搜索範圍內的算法

Question

我給出了一個具有屬性x和y的對象的巨大列表。我們需要搜索位於兩個屬性的給定上限和下限之間的所有對象。

我想知道是否有一個有效的算法來實現這一點。

謝謝！

Answer 1

四叉樹或空間索引（空間填充曲線，例如希爾伯特曲線）。

Answer 2

有這樣的標準算法。請參閱http://en.wikipedia.org/wiki/R-tree。