在範圍列表上執行查找

Question

我有我想查詢範圍的列表。範圍是按順序並且不重疊。

例：

1-10，11-17 ， 18-20，21-30 ， 等等

目前我使用修改後的二進制搜索。但是我現在有了一個新的列表......除了非重疊範圍之外，新列表還可以掩蓋範圍。

例：

0-255， 256-287， 288-303， 等等

有一對夫婦一千範圍內，在大約500,000

我結束我會在c中實現它，但是語言並不重要。我只是想找一些關於如何利用這個新房產的想法。有沒有人遇到過/讀過它？如果有人有任何想法，他們會受到歡迎。 :)

Answer 1

拿着一個大小爲500000的位向量怎麼樣？這將需要大約61kb。

然後，您可以通過執行AND來查詢數字是否在O（1）的範圍內。您也可以同時查詢多個值。此外，設置範圍位矢量將非常快，因爲您不需要排序。