如何找到一個數字是否包含在數組範圍內的數組中

我有一個java對象數組。如何找到一個數字是否包含在數組範圍內的數組中

每個對象存儲兩個定義數字範圍的長整數。
我已經保證對於範圍內的所有對象，數字範圍不會重疊。

我想快速找到數組中的特定對象，給定一個可能（或可能不）屬於由對象定義的數字範圍之一的數字。

我一直希望使用Array.binarySearch來做這件事，但看起來並不合適。

有關最佳方式的任何想法？

來源

2009-07-01 tomdee

數組以任何方式排序？ – Erix 2009-07-01 15:10:47

Array.binarySearch需要事先對您的數組進行排序。是嗎？ – 2009-07-01 15:10:54

不，它沒有排序。對數組進行排序似乎很容易，但是二進制搜索更困難，因爲我試圖找到一個落在範圍內的數字。 – tomdee 2009-07-02 14:50:25

使用TreeMap。關鍵是兩個長距離範圍中的較低者;值是對象。

private TreeMap<Long, T> map = new TreeMap<Long, T>(); 

void insertObject(T object) { 
    map.put(object, object.getLowerRangeBoundary()); 
} 

T getObjectByKeyInRange(Long query) { 
    // Get the first Object in the tree that corresponds with the query 
    Map.Entry<Long, T> e = map.floorEntry(query); 

    // If there's no entry, then the query value is lower than all ranges in the tree 
    if (e == null) { 
     return null; 
    } 

    T target = e.getValue(); 
    // "target" is the only object that can contain the query value 
    // If the query value is within the range of "target", then it is our object 
    if (query < target.getUpperRangeBoundary()) { 
     return target; 
    } 

    // Nobody has the query value in their range; return null 
    return null; 
}

來源

2009-07-01 15:24:28 jprete

如果a.start> b.end，讓數組中的項目實現Comparable接口，讓項目a比另一個項目b更大。然後使用此比較對數組進行排序。

然後要查找數字x是否在數組中的某個範圍內，請在數組中搜索k.end> = x的第一個項目k，並檢查k.start < = x 。如果是這樣，k是範圍。否則，x不在數組中的任何範圍內。

來源

2009-07-01 15:13:01 drvdijk

實際上，你可以處理這個問題非常有效（對大量範圍的數以百萬計的查詢的範圍）和允許重疊範圍。

僞代碼：

設rangeMap是一個TreeMap：

foreach(Range r in ranges) 
    rangeMap[r.start].Increment(); 
    rangeMap[r.end].Decrement();

rangeMap.GreatestLowerBound（我）現在將返回範圍的數量，一個給定的整數i屬於（即GreatestLowerBound是最大的號碼< = i）。

如果您知道前面的範圍數量，您可以在實際性能方面做得更好......通過分配單個數組，使用「deltaRange」填充它，然後「整合」以獲得顯示累積每個數字x的「範圍」。

來源

2009-07-01 15:47:06

如何找到一個數字是否包含在數組範圍內的數組中

回答

相關問題