A SortedList.IndexOfKey(key) 返回项目的索引，其中 item.key >= key

Question

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

这是否意味着如果我想在列表中查找大于或等于 key 的键的索引，我必须自己实现二分搜索？或者有什么开箱即用的东西被我忽略了？

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

（一般来说，我希望拥有类似Java的NavigableMap功能，即对排序的地图/字典进行高效迭代之类的功能，但现在，上述问题的答案就足够了，我可以用我的方式“扩展方法”从那里以某种方式）

Answer 1

所以，对于包括我自己在内的子孙后代，我再次需要 .net 中的 NavigableMap。适用于 SortedList 的 BinarySearch 扩展方法以及适用于任何 IList 的重载。

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;
    }
}

注意：我想知道为什么 .net 中没有 IRandomAccess，至少可以派生出 IList 和数组。

SortedList 实际上可以派生自 IRandomAccess，以及 IRandomAccess 和 IRandomAccess>。

Answer 2

恐怕你不走运，没有任何内置的东西。

如果您为 IList 创建二分搜索扩展方法，则可以将其用于 Keys 属性。这有点烦人，但不太困难。

（框架的内置二进制搜索方法使用的约定 - Array 和 List -- 是在没有找到该元素时返回下一个元素索引的按位补码。）

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