title: Is there a Lower Bound function on a SortedList<K ,V>?
body: <p>Is there a Lower Bound function on a <code>SortedList&lt;K ,V&gt;</code>? The function should return the first element equal to or greater than the specified key. Is there some other class that supports this?</p>
  
  <p>Guys - please read the question once again. <strong>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.</strong></p>
  
  <p><strong>I'm interested in O(log n) time</strong>. It means that I do not have a problem with foreach loop, but rather would like to have an efficient way of doing this.</p>
  
  <p>I have done some tests on this.</p>
  
  <p>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:</p>
  
  <pre><code>public static int FindFirstIndexGreaterThanOrEqualTo&lt;T&gt;(
              this IList&lt;T&gt; sortedCollection, T key
          ) where T : IComparable&lt;T&gt; {
      int begin = 0;
      int end = sortedCollection.Count;
      while (end &gt; begin) {
          int index = (begin + end) / 2;
          T el = sortedCollection[index];
          if (el.CompareTo(key) &gt;= 0)
              end = index;
          else
              begin = index + 1;
      }
      return end;
  }
  </code></pre>