排序列表的鍵上的二進制搜索<K, V>

Question

我需要編寫一些線性插值的代碼，我試圖找出最有效的方式來搜索圍繞我的目標鍵的上下鍵的SortedList<K, V>的鍵。

SortedList<int, double> xyTable = new SortedList<int, double>() 
{ 
    {1, 10}, {2, 20}, {3, 30}, {4,40} 
}; 

double targetX = 3.5; 

什麼是最有效的方式來搜索列表並確定3.5是3和4之間？我有一個方法/作弊的整數（臨時插入目標鍵到列表中，然後找到索引），但我想我會問專業人員，所以我可以產生高質量的代碼。

謝謝。

Answer 1

二分查找爲您在列表中提供良好的性能。但SortedList上的Keys屬性類型爲IList，而BinarySearch定義爲List。幸運的是，你可以在此相關的問題找到IList二進制搜索的實現：

How to perform a binary search on IList<T>?

Answer 2

public class Bounds 
{ 
    int lower; 
    int upper; 

    public Bounds(int lower, int upper) 
    { 
     this.lower = lower; 
     this.upper = upper; 
    } 
} 

public Bounds BinarySearch(List<int> keys, double target) 
{ 
    // lower boundary case returns the smallest key as the lower and upper bounds 
    if (target < keys[0]) 
     return new Bounds(0, 0); 

    else if (target < keys[1]) 
     return new Bounds(0, 1); 

    // upper boundary case returns the largest key as the lower and upper bounds 
    else if (target > keys[keys.Length - 1]) 
     return new Bounds(keys.Length - 1, keys.Length - 1); 

    else if (target > keys[keys.Length - 2]) 
     return new Bounds(keys.Length - 2, keys.Length - 1); 

    else 
     return BinarySearch(keys, target, 0, keys.Length - 1); 

} 

// 'keys' is a List storing all of the keys from your SortedList. 
public Bounds BinarySearch(List<int> keys, double target, int lower, int upper) 
{ 
    int middle = (upper + lower)/2; 

    // target is equal to one of the keys 
    if (keys[middle] == target) 
     return new Bounds(middle - 1, middle + 1); 

    else if (keys[middle] < target && keys[middle + 1] > target) 
     return new Bounds(middle, middle + 1); 

    else if (keys[middle] > target && keys[middle - 1] < target) 
     return new Bounds(middle - 1, middle); 

    if (list[middle] < target) 
     return BinarySearch(list, target, lower, upper/2 - 1); 

    if (list[middle] > target) 
     return BinarySearch(list, target, upper/2 + 1, upper); 
} 

這可能work..I沒有測試出來。如果沒有，希望它足夠接近，你可以稍微調整使用它。這是一個奇怪的問題，所以我處理了所有的邊界情況，所以我不必考慮當範圍降低到2個元素或更少時算法會執行什麼操作。

Answer 3

在我的情況下，源SortedList沒有太大的變化，因爲它被用作查找表。所以在這種情況下，將SortedList轉換爲List<T>一次是有意義的。之後，它是很容易使用內置的List<T>二分查找方法...

double targetX = 3.5; 

// Assume keys are doubles, may need to convert to doubles if required here. 
// The below line should only be performed sparingly as it is an O(n) operation. 
// In my case I only do this once, as the list is unchanging. 
List<double> keys = xyTable.Keys.ToList(); 

int ipos = keys.BinarySearch(targetX); 

if (ipos >= 0) 
{ 
    // exact target found at position "ipos" 
} 
else 
{ 
    // Exact key not found: BinarySearch returns negative when the 
    // exact target is not found, which is the bitwise complement 
    // of the next index in the list larger than the target. 
    ipos = ~ipos; 
    if (ipos >= 0 && ipos < keys.Count) 
    { 
     if (ipos > 0) 
     { 
      // target is between positions "ipos-1" and "ipos" 
     } 
     else 
     { 
      // target is below position "ipos" 
     } 
    } 
    else 
    { 
     // target is above position "ipos" 
    } 
} 

Answer 4

從MSDN，

的一個排序列表對象由按鍵排序元素或者根據特定的IComparer在創建SortedList時指定的實現，或根據密鑰本身提供的IComparable實現。 索引序列基於排序順序。當添加一個元素時，它會以正確的排序順序插入到SortedList中，並且索引會相應地進行調整。當元素被移除時，索引也會相應地進行調整。因此，特定鍵/值對的索引可能隨着元素從SortedList添加或刪除而改變。

*****此方法使用二進制搜索算法;因此，這種方法是O（log n）的操作，其中n是計數。*****

與.NET Framework 2.0開始，該方法使用該集合的對象的Equals和的CompareTo方法關於項目，以確定是否存在項目。在早期版本的.NET Framework中，通過使用集合中對象的item參數的Equals和CompareTo方法進行此確定。

換句話說，SortedList中的IndexOfKey方法實際上已經使用了binarySearch算法，因此在您的情況下不需要將表單SortedList轉換爲List。

希望它可以幫助..