在Java中的範圍查找

Question

假設，我有一個重疊ranges未排序的數組。每個range只是一對整數begin和end。現在我想查找給定的key是否屬於ranges中的至少一個。也許，我必須知道它也屬於ranges。

我們可以假設ranges數組需要〜1M並適合內存。我正在尋找一種簡單的算法，它只使用標準的JDK集合，沒有任何3d方庫和特殊的數據結構，但工作速度相當快。

你會建議什麼？

Answer 1

如果你不需要知道其中區間包含你的觀點（編輯：我想你可能做的，但我會離開這個答案的人有這個問題，誰不），然後

1. 通過計算兩個數組B和E來預處理間隔.B是以排序順序開始的值。 E是按排序順序結尾的值。

2. 要查詢點x，使用二進制搜索找到最小索引i，使得B [i]> x和最小索引j使得E [j]≥x。包含x的區間數[begin，end]是i - j。

---

class Interval { 
    double begin, end; 
} 

class BeginComparator implements java.util.Comparator<Interval> { 
    public int compare(Interval o1, Interval o2) { 
     return Double.compare(o1.begin, o2.begin); 
    } 
}; 

public class IntervalTree { 
    IntervalTree(Interval[] intervals_) { 
     intervals = intervals_.clone(); 
     java.util.Arrays.sort(intervals, new BeginComparator()); 
     maxEnd = new double[intervals.length]; 
     initializeMaxEnd(0, intervals.length); 
    } 

    double initializeMaxEnd(int a, int b) { 
     if (a >= b) { 
      return Double.NEGATIVE_INFINITY; 
     } 
     int m = (a + b) >>> 1; 
     maxEnd[m] = initializeMaxEnd(a, m); 
     return Math.max(Math.max(maxEnd[m], intervals[m].end), initializeMaxEnd(m + 1, b)); 
    } 

    void findContainingIntervals(double x, int a, int b, java.util.Collection<Interval> result) { 
     if (a >= b) { 
      return; 
     } 
     int m = (a + b) >>> 1; 
     Interval i = intervals[m]; 
     if (x < i.begin) { 
      findContainingIntervals(x, a, m, result); 
     } else { 
      if (x <= i.end) { 
       result.add(i); 
      } 
      if (maxEnd[m] >= x) { 
       findContainingIntervals(x, a, m, result); 
      } 
      findContainingIntervals(x, m + 1, b, result); 
     } 
    } 

    java.util.Collection<Interval> findContainingIntervals(double x) { 
     java.util.Collection<Interval> result = new java.util.ArrayList<Interval>(); 
     findContainingIntervals(x, 0, intervals.length, result); 
     return result; 
    } 

    Interval[] intervals; 
    double[] maxEnd; 

    public static void main(String[] args) { 
     java.util.Random r = new java.util.Random(); 
     Interval[] intervals = new Interval[10000]; 
     for (int j = 0; j < intervals.length; j++) { 
      Interval i = new Interval(); 
      do { 
       i.begin = r.nextDouble(); 
       i.end = r.nextDouble(); 
      } while (i.begin >= i.end); 
      intervals[j] = i; 
     } 
     IntervalTree it = new IntervalTree(intervals); 
     double x = r.nextDouble(); 
     java.util.Collection<Interval> result = it.findContainingIntervals(x); 
     int count = 0; 
     for (Interval i : intervals) { 
      if (i.begin <= x && x <= i.end) { 
       count++; 
      } 
     } 
     System.out.println(result.size()); 
     System.out.println(count); 
    } 
} 

Answer 2

排序定製Comparator數值範圍內時，則對於每個關鍵ķ構建一個元素的範圍[ķ，ķ]，然後針對該範圍內的binary search具有不同Comparator。

的Comparator用於搜索的compare(x,y)應該返回

• <0如果x.max < y.min
• >0如果x.min > y.max
• 0否則（它的兩個參數範圍重疊）。

正如@Per指出的那樣，您需要一個不同的，更嚴格的Comparator進行排序，但前兩個子句仍然存在。

這應該工作，即使範圍重疊，雖然你可能要合併排序，以加快搜索後重疊範圍。合併可以在O（N）時間完成。

這實際上是一個靜態interval tree，即一個沒有O（LG Ñ）插入或缺失，以同樣的方式，一個排序後的數組可以被認爲是靜態二進制搜索樹。

Answer 3

我相信這是你在找什麼：http://en.wikipedia.org/wiki/Interval_tree

但首先檢查這個簡單的解決方案，看它是否適合您的需要：Using java map for range searches

Answer 4

簡單的解決方案與O（n）的複雜性：

for(Range range: ranges){ 
    if (key >= range.start && key <= range.end) 
    return range; 
} 

如果我們知道更多關於範圍的信息，就可以應用更聰明的算法。 他們排序了嗎？它們重疊嗎？等

Answer 5

由於只是你的規範，我會傾向於通過規模首次訂購的範圍，具有最寬的範圍（使用自定義的比較，以方便這一點）。然後只需遍歷它們並在找到包含該鍵的範圍後立即返回true。因爲我們對數據一無所知，當然最寬的範圍是最可能包含給定密鑰的;首先搜索它們可能是（小）優化。

，你可以在進行預處理其他方式列表。例如，您可以排除任何完全被其他範圍包圍的範圍。只要您遇到比您的密鑰更大的begin值，您可以訂購begin並提早退出。