Is there a Lower Bound function in C# on a SortedList?

Question

Is there a Lower Bound function in C# on a SortedList? 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.

Also I didn't mention it, but 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;
}

Answer 1

Binary search the SortedList.Keys collection.

Here we go (this is O(logn) unless there are equal keys in the sorted list, in which case, nothing special can be done about it).

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

public static int BinarySearch<T>(this IList<T> sortedCollection, T value) where T : IComparable<T>
{
    if (sortedCollection == null)
        throw new ArgumentNullException("sortedCollection");

    int begin = 0;
    int end = sortedCollection.Count - 1;
    int index = 0;
    while (end >= begin) {
        index = (begin + end) / 2;
        T val = sortedCollection[index];
        if (value == null && val == null)
            return index;
        int compare = val.CompareTo(value);
        if (compare == 0) 
            return index;
        if (compare > 0)
            end = index - 1;
        else
            begin = index + 1;
    }

    return ~index; // Not found, return bitwise complement of the index.
}

public static int FindFirstIndexGreaterThanOrEqualTo<T>(this IList<T> sortedCollection, T value) where T : IComparable<T>
{
    int index = BinarySearch(sortedCollection, value);
    if (index < 0)
        index = ~index;
    while (index < sortedCollection.Count && sortedCollection[index].CompareTo(value) < 0)
        index++;
    while (index > 0 && sortedCollection[index - 1].CompareTo(value) == 0)
        index--;

    return index;
}

Answer 2

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.

Answer 3

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)

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.