甲SortedList.IndexOfKey（鍵），該返回的項的索引，其中item.key> =鍵

排序列表< TKEY的，TValue > .IndexOfKey（鍵）返回-1，如果鍵是未在列表中。甲SortedList.IndexOfKey（鍵），該返回的項的索引，其中item.key> =鍵

這是否意味着如果我想在列表中找到大於或等於密鑰的密鑰的索引，我必須自己實現二分搜索？或者我忽略了一些開箱即用的東西？

我當然想得到O（log（n））的結果，所以請不要LINQ迭代和過濾魔術。（一般來說，我想要有類似Java的NavigableMap功能，比如對有序的地圖/字典進行高效迭代等功能，但現在對上述問題的回答就足夠了，我可以「擴展 - 方法「我的方式從那裏以某種方式）

來源

2012-01-27 Eugene Beresovsky

其非常奇怪List有二進制搜索，但SortedList沒有二分搜索。 – 2017-09-22 21:06:43

恐怕你運氣不好，沒有什麼內置的。

如果您爲IList<T>創建二進制搜索擴展方法，那麼您可以將其用於Keys屬性。這有點煩人，雖然不是太困難。

（由所使用的約定框架內置的二進制搜索方法 - Array和List<T> - 是返回的下一個元素的索引的位元補時未找到該元素）

int index = yourSortedList.Keys.YourBinarySearchExtensionMethod(key); 
if (index >= 0) 
{ 
    // key found 
} 
else 
{ 
    // key not found 
}

來源

2012-01-27 11:12:29 LukeH

感謝您指出內置列表 .BinarySearch方法。這樣，所剩下的只是一點管道工。（不是說實現二進制搜索需要任何博士學位） – 2012-01-29 02:32:26

所以在這裏是爲了後代，包括我自己，因爲我還需要在.net中使用NavigableMap。 BinarySearch適用於SortedList<TKey, TValue>的擴展方法以及適用於任何IList<T>的超載。

public static class BinarySearch4All 
{ 
    public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> sortedList, 
      TKey value, IComparer<TKey> comparer = null) 
    { 
     return BinarySearch(sortedList, 0, sortedList.Count, value, comparer); 
    } 

    public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> sortedList, 
      int index, int length, TKey value, IComparer<TKey> comparer = null) 
    { 
     return BinarySearch(sortedList.Keys, index, length, value, comparer); 
    } 

    public static int BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer = null) 
    { 
     return BinarySearch(list, 0, list.Count, value, comparer); 
    } 

    // algorithm courtesy of http://referencesource.microsoft.com/#mscorlib/system/collections/generic/arraysorthelper.cs#114ea99d8baee1be 
    public static int BinarySearch<T>(this IList<T> list, int index, int length, 
      T value, IComparer<T> comparer = null) 
    { 
     if (comparer == null) 
      comparer = Comparer<T>.Default; 
     int lo = index; 
     int hi = index + length - 1; 
     while (lo <= hi) 
     { 
      int i = lo + ((hi - lo) >> 1); 
      int order = comparer.Compare(list[i], value); 

      if (order == 0) return i; 
      if (order < 0) 
       lo = i + 1; 
      else 
       hi = i - 1; 
     } 
     return ~lo; 
    } 
}

N.B.我想知道爲什麼在.net中沒有IRandomAccess<T>，至少有IList<T>和數組可以從中得到。

SortedList<TKey, TValue>實際上可以從IRandomAccess<TKey>以及IRandomAccess<TValue>和IRandomAccess<KeyValuePair<TKey, TValue>>得出。

來源

2014-06-09 12:41:41

甲SortedList.IndexOfKey（鍵），該返回的項的索引，其中item.key> =鍵

回答

相關問題