A SortedList.IndexOfKey(key) that returns the index of the item where item.key >= key

Question

SortedList<TKey, TValue>.IndexOfKey(key) returns -1 if key is not in the list.

Does this mean I have to implement a binary search myself if I want to find the index of the key in the list that is greater or equal to key? Or is there something out of the box that I overlooked?

I want to get the result in O(log(n)) of course, so please no LINQ iterate and filter magic.

(In general, I'd like to have something like Java's NavigableMap functionality, i.e. features like efficient iteration over a sorted map/dictionary, but for now, an answer to the above question would suffice, I can "extension-method" my way from there somehow)

Answer 1

So here it is, for posterity, including myself, as I'm yet again in need of a NavigableMap in .net. BinarySearch extension methods that work for SortedList<TKey, TValue> and overloads that work for any 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. I wonder why there is no IRandomAccess<T> in .net, which at least IList<T> and arrays would derive from.

SortedList<TKey, TValue> could actually derive from IRandomAccess<TKey>, as well as IRandomAccess<TValue> and IRandomAccess<KeyValuePair<TKey, TValue>>.