Is there a Lower Bound function on a SortedList<K ,V>?

Question

Is there a Lower Bound function on a SortedList<K ,V>? The function should return the first element equal to or greater than the specified key. Is there some other class that supports this?

Guys - please read the question once again. I do not need a function that returns the key if it is present. I'm interested in scenario when there is no exact key matching.

I'm interested in O(log n) time. It means that I do not have a problem with foreach loop, but rather would like to have an efficient way of doing this.

I have done some tests on this.

Linq statements are not optimized by neither the compiler nor runtime machine, so they walk through all collection elements and are slow O(n). Based on Mehrdad Afshari answer, here is a Binary Search that works in O(log n) on the Keys collection:

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
            this IList<T> sortedCollection, T key
        ) where T : IComparable<T> {
    int begin = 0;
    int end = sortedCollection.Count;
    while (end > begin) {
        int index = (begin + end) / 2;
        T el = sortedCollection[index];
        if (el.CompareTo(key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}

Cordoba

Answer 1

Binary search the SortedList.Keys collection.

Here we go. This is O(log n):

private static int BinarySearch<T>(IList<T> list, T value)
{
    if (list == null)
        throw new ArgumentNullException("list");
    var comp = Comparer<T>.Default;
    int lo = 0, hi = list.Count - 1;
    while (lo < hi) {
            int m = (hi + lo) / 2;  // this might overflow; be careful.
            if (comp.Compare(list[m], value) < 0) lo = m + 1;
            else hi = m - 1;
    }
    if (comp.Compare(list[lo], value) < 0) lo++;
    return lo;
}

public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
                          (this SortedList<T,U> sortedList, T key)
{
    return BinarySearch(sortedList.Keys, key);
}

Maturity

Isn't the collection generated every time we read Keys property? – Cordoba

agsamek: Nope, it's not regenerated. It'll return an instance of internal class KeyList which provides direct access to the elements in the original collection. Nothing is copied in the process. – Maturity

The "no copy for Keys and Values" is the main diference with a SortedDictionary – Deceptive

A minor quibble, but I believe this does not correctly handle the edge case of all values in the list being less than the key. This example returns n, but it should return -1 (or throw exception). – Jenine

@Jenine You are right. It will return 0 in that case, which might or might not be the desired result depending on the context. In any case, that can be fixed with an if statement. – Maturity

@ralu You can't do this without a linear search on a Dictionary. – Maturity

To avoid the overflow: var m = low + (hi - low)/2 – Disherison

When the list is empty, this method throws an exception... it should return 0, shouldn't it ? – Rathbone

This repo contains the implementation of lower_bound() and upper_bound() for C# Array, List, and SortedList classes: github.com/mohanadHamed/MNDSearchUtil – Hanse

Isn't this O(log(2)N)? – Semantics

@Semantics O(log(n, base1)) == O(log(n, base2)) for all valid bases. proof: log(n, base1) = log(n, base2) * log(base1, base2) and log(base1, base2) is a constant which makes it asymptotically irrelevant. So you can omit the base when talking about O(log(..)) of something – Maturity

But assumed that the complexity of a call to list[m] is itself logarithmic, the whole function's complexity evaluates to O(log(n)²), doesn't it? – Beady

Well, it's worth mentioning that there is a difference between just List<T> and SortedList<T> in terms of time complexity. Although you use IList<T> for BinarySearch function the time complexity will be different for SortedList<T> as accessing an element at random index is O(log n). So, the resulted complexity of this method is O(log² n). – Ginsberg

In the case where all list values are less than the searched value (key), the final lo++ will ensure we return list.Count, as @Jenine noted. Therefore, to make the function handle the case of an empty list and avoid out of bound exception on the final list[lo] access, to follow the same convention, we should add if (list.Count == 0) return 0; Of course, returning -1, etc. is also okay, but if we pick this convention then we should do it for all these cases (basically on start, if (list.Count == 0 || comp.Compare(list[^1], value) < 0) return -1;) – Mm

Why not just use Array.BinarySearch on the keys? – Gillum

Answer 2

I'd go with LINQ (presuming you're using C#3), but using the overload of FirstOrDefault that takes a predicate:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

(a lot of the other Enumerable methods can also take predicates which is a nice shortcut)

Greet

Answer 3

Not aware of one, but it's a simple LINQ statement:

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();

first will either be the first object that passes the comparison or default(T) (which is normally null).

Edit

DaveW's version:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

does the same job but could potentially be faster, you'd have to test it though.

Danyelldanyelle

Answer 4

Or you can write own extension method to do this. Note that all those functions are NOT guaranteed to go in a sequesce.

Latticework

Answer 5

public static TValue? LowerBound<TKey, TValue>(this SortedList<TKey, TValue> list, TKey key) where TKey : notnull, IComparable<TKey>
{
    var comparer = list.Comparer;

    #region Short-Circuits

    if (list.Count == 0) //empty list
        return default;
    if (list.ContainsKey(key)) 
       return list[key]; //"The function should return the first element equal"

    if (comparer.Compare(list.Keys[list.Keys.Count - 1], key) < 0)
        return default; // if all elements are smaller, return default

    if (comparer.Compare(list.Keys[0], key) > 0)
        return list[list.Keys[0]]; //if the first element is greater, return it

    #endregion Short-Circuits

    int range = list.Count - 1; //the range between of first and last element to check
    int itemIndex = 1;          //the default value of index is 1 since 0 was already checked above
    while (range > 0)
    {
        int halfRange = range / 2;               //cut the search range in half
        int indexTmp = itemIndex + halfRange;    //set the current item to compare
        if (comparer.Compare(list.Keys[indexTmp], key) < 0)
        {
            //the current item is less than the given key
            itemIndex = indexTmp + 1;   //set the current item to the item after the compared item
            range = (range - halfRange - 1); //move the remaining range to the right
        }
        else
        {
            //the current item is greater than the given key (we have already checked equal above in short-circuits)
            range = halfRange; //move the remaining range to the left
        }
    }
    return list[list.Keys[itemIndex]];
}

Cupping

OK, this one is convenient to get the value directly (as asked by the OP). In counterpart, we don't distinguish the case where the list was empty / the searched key was greater than all keys, and we happened to find a value at the lower bound, just equal to the default value. But this is okay if the default value is invalid, or we know that there should be a lower bound, or we really want that default is there is no lower bound. In addition, we can make the function return a bool of success + an out TValue if we really want to preserve this information. If you need the index, see mmx's answer. – Mm

Answer 6

Hopefully this should be faster, depending on SortedList's implementation.

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
        this SortedList<K, V> sortedCollection, K key
    ) where V : new()
{
    if (sortedCollection.ContainsKey(key))
    {
        return sortedCollection.IndexOfKey(key);
    }
    sortedCollection[key] = new V();
    int retval = sortedCollection.IndexOfKey(key);
    sortedCollection.Remove(key);
    return retval;
}

Typify