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

I'm afraid you're out of luck, there's nothing built-in.

If you create a binary search extension method for IList<T> then you could use it against the Keys property. This is a bit annoying, though not too difficult.

(The convention used by the framework's built-in binary search methods -- Array and List<T> -- is to return the bitwise complement of the index of the next element when the element isn't found.)

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

Answer 2

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>>.