1
假設您有一個整數n。讓我們假設你有不重疊的整數範圍的列表，例如：檢測整數是否在多個有效整數範圍內
1-9
99-105
160-205
503-600
// many more thousands of ranges, etc ....
我可以很容易地遍歷所有的這些，並檢查是否n是每個界之間，並返回true，如果是。那將是O（n），這是不好的。這可以在O（1）中完成嗎？
一些規則：
- 的整數本身非常大，範圍非常廣泛，所以它不會是可行的，只是獲得可接受的整數的完整列表，並使用類似的一套做的Ø （1）查找。將許多整數存儲在內存中太昂貴了。我只能存儲邊界列表。
- 我打算多次運行這個測試，所以我可以將列表製作成一些數據結構，如果這使得後續查找效率更高。
我覺得我可以得到這些範圍的二進制表示，並構建一棵可以產生O（log（n））的樹。
我真正的問題
我有IP地址的子網列表。我需要測試給定的IP是否在任何這些子網中。我將有許多IP來檢查。我可以將IP轉換爲整數（1.2.3.4 => 1 * 2^32 + 2 * 2^16 + 3 * 2^8 + 4）。我可以類似地轉換子網。這等同於上面的「更簡單解釋」問題。
謝謝！