.net - SortedList.IndexOfKey(key) 返回 item.key >= key 的项目的索引

Question

如果键不在列表中，SortedList .IndexOfKey(key) 返回 -1。

这是否意味着如果我想在列表中找到大于或等于键的键的索引，我必须自己实现二分搜索？还是我忽略了一些开箱即用的东西？

我当然想得到 O(log(n)) 的结果，所以请不要使用 LINQ 迭代和过滤魔法。

(一般来说，我想要像 Java 的 NavigableMap 功能这样的功能，即在排序的 map /字典上进行高效迭代等功能，但就目前而言，上述问题的答案就足够了，我可以按照自己的方式“扩展方法”从那里以某种方式)

Answer 1

所以，为了后代，包括我自己，我再次需要一个 NavigableMap在.net中。 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;
    }
}

注意我想知道为什么没有 IRandomAccess<T>在 .net 中，至少 IList<T>和数组将派生自。
SortedList<TKey, TValue>实际上可以源自 IRandomAccess<TKey> ，以及 IRandomAccess<TValue>和 IRandomAccess<KeyValuePair<TKey, TValue>> .